Table of contents

코딜리티 Distinct

배열에서 중복되지 않는 수를 반환하는 문제이다. N의 범위가 0부터 100000이기 때문에 O(N) 또는 O(N log N) 복잡도가 필요하다.

풀이

O(N log N) || O(N)

이번 문제는 쉬운 문제지만, 병합 정렬 코드를 기록할 겸 포스팅을 작성한다.

중복되지 않는 수를 구하는 알고리즘은 배열을 정렬 한 뒤, 이전 인덱스의 요소와 같지 않은 요소의 숫자를 count 하며, count 자체를 결과로 반환한다.

  • A[] = 1, 2, 1, 2, 3, 1, 정렬된 A[] = 1, 1, 1, 2, 2, 3
  • 정렬된 배열은 1부터 시작할 것이기 떄문에 count를 1로 가정하고 시작해야 한다.
  • count = 1, index = 1으로 시작, 매 반복마다 index++
    • A[1] != A[0] ? -> X (1 == 1), count = 1
    • A[2] != A[1] ? -> X (1 == 1), count = 1
    • A[3] != A[2] ? -> O (2 != 1), count = 2
    • A[4] != A[3] ? -> X (2 == 2), count = 2
    • A[5] != A[4] ? -> O (3 != 2), count = 3
  • 결과 3
private int distinct(int[] A) {
    if (A.length == 0) return 0;
    sort(A);
    int result = 1;
    for (int i = 1; i < A.length; i++) {
        if (A[i] != A[i - 1]) {
            result += 1;
        }
    }
    return result;
}

int[] sorted;
private void sort(int[] A) {
    sorted = new int[A.length];
    mergeSort(A, 0, A.length - 1);;
}

// 분할
private void mergeSort(int[] A, int start, int end) {
    if (start >= end) {
        return;
    }

    int middle = (start + end) / 2;
    mergeSort(A, start, middle);
    mergeSort(A, middle + 1, end);
    merge(A, start, middle, end);
}

// 병합
private void merge(int[] A, int start, int middle, int end) {
    int i = start;
    int j = middle + 1;
    int k = start;

    while (i <= middle && j <= end) {
        if (A[i] <= A[j]) {
            sorted[k++] = A[i++];
        } else {
            sorted[k++] = A[j++];
        }
    }

    while (i <= middle) {
        sorted[k++] = A[i++];
    }

    while (j <= end) {
        sorted[k++] = A[j++];
    }

    for (int t = start; t <= end; t++) {
        A[t] = sorted[t];
    }
    print(A);
}

k는 sorted 배열, i는 왼쪽 배열, j는 오른쪽 배열의 인덱스이다.

정리

병합정렬에 대한 설명은 여기 를 참고하면 좋을 것 같다. 일단 분할하고, 정렬하면서 병합한다는 내용과 O(N log N)의 시간 복잡도, O(N)의 공간 복잡도는 이해가 가는데, 코드에서 헷갈리는 부분이 있었다.

while (i <= middle) {
	sorted[k++] = A[i++];
}

while (j <= end) {
	sorted[k++] = A[j++];
}

위에서 정렬하여 sorted에 값을 설정해줬는데, 왜 또 왼쪽과 오른쪽을 다시 sorted에 설정하는지 이해가 가질 않았다. 우선 위위 코드를 지우지 않은 상태에서의 진행 과정과 위의 코드를 지운 상태에서의 진행 과정을 살펴보자.

1. 코드를 지우지 않은 상태
2 1 1 2 3 1 
1 2 1 2 3 1 
1 1 2 2 3 1 
1 1 2 2 3 1 
1 1 2 1 2 3 
1 1 1 2 2 3 

2. 코드를 지운 상태
1 2 1 2 3 1 
1 0 1 2 3 1 
1 0 0 2 3 1 
1 0 0 2 0 1 
1 0 0 1 0 0 
1 0 0 1 0 0

코드를 지운 상태에서 보면 0이 중간 중간에 들어가면서 배열이 망가진다는 것을 알 수 있다. 예를 들어 1과 2를 비교하여 병합한다고 생각해보자. i = 0, k = 0; j = 1인 상태에서 병합을 시작한다. sorted[k]에 A[i]가 들어가면서 i는 1이 되지만, j는 아직 1이다. j가 변하지 않았다는 의미는 아직 j번째 요소가 sorted 배열에 들어가지 않았음을 의미한다. 그래서 1이 들어간 이후의 자리에 아직 병합되지 않은 요소를 병합한다. 2와 1을 비교 하는 경우도 i가 움직이는 것 말고는 똑같다.

참고로 병합정렬은 퀵 정렬보다 전반적으로 더딘 성능을 보여주지만, 데이터의 상태에 별 영향을 받지 않는다는 장점이 있다.

추가적인 메모리 없이 병합 정렬을 수행할 수도 있지만, 그 경우 시간복잡도가 O(n(lgn)2)으로 늘어난다.