[백준/C언어] 18870번 - 좌표 압축

백준 웹사이트 "18870번 - 좌표 압축" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

18870번: 좌표 압축

---

소스 코드

#include <stdio.h>

void merge_sort(int *arr, int index, int len);
void merge(int *arr, int l_index, int r_index, int l_len, int r_len);
int binary_search(int * arr, int element, int start, int end);

int main(void){
    int N;
    scanf("%d", &N);

    int num[N];
    int num_sort[N];    //정렬시킬 num 배열

    for(int i=0; i<N; i++){
        scanf("%d", &num[i]);
        num_sort[i] = num[i];
    }
    
    merge_sort(num_sort, 0, N); 
    //num: 정렬 전 배열, num_sort: 정렬 후 배열
    //num_order: num_sort 내에서 중복 제거한 배열
    int num_order[N];
    int count=0;
    for(int i=0; i<N; i++){
        if(i>0 && num_sort[i]!=num_sort[i-1])
            count++;
        num_order[count] = num_sort[i];
    }

    for(int i=0; i<N; i++){ //시간 복잡도: O(n)*O(logn)=O(nlogn)
        int idx = binary_search(num_order, num[i], 0, count);    //시간 복잡도: O(logn)
        printf("%d ", idx);
    }
}

void merge_sort(int *arr, int index, int len){
    // Base Case
    if(len==1){
        return;
    }

    // Recursive Case
    // 1. arr을 반으로 나눈다
    int left = index;
    int right = index + len/2;
    int left_len = len/2;
    int right_len = len - len/2;

    // 2. 왼쪽, 오른쪽을 각각 merge_sort 한다
    merge_sort(arr, left, left_len);
    merge_sort(arr, right, right_len);

    // 3. 왼쪽, 오른쪽을 merge 한다
    merge(arr, left, right, left_len, right_len);
}

void merge(int *arr, int l_index, int r_index, int l_len, int r_len){
    // 1. 임시 배열 선언
    int temp[l_len+r_len];
    int count = 0;
    
    // 2. 왼쪽, 오른쪽의 가장 작은 수 비교
    int l_count = 0;
    int r_count = 0;
    while(1){
        int left = l_index + l_count;
        int right = r_index + r_count;

        if(arr[left] <= arr[right]){
            temp[count] = arr[left];
            count++;
            l_count++;
        }
        else{
            temp[count] = arr[right];
            count++;
            r_count++;
        }

    // 3. 왼쪽이나 오른쪽의 끝에 도달하면 break
        if(l_count==l_len || r_count==r_len){
            break;
        }
    }

    // 4. 남은 요소 temp로 복사
    if(l_count==l_len){ // 오른쪽을 복사
        while(count<l_len+r_len){
            temp[count] = arr[r_index+r_count];
            count++;
            r_count++;
        }
    }
    else{               // 왼쪽을 복사
        while(count<l_len+r_len){
            temp[count] = arr[l_index+l_count];
            count++;
            l_count++;
        }
    }

    // 5. arr에 임시배열 복사
    for(int i=l_index; i<l_index+l_len+r_len; i++){
        arr[i] = temp[i-l_index];
    }
}

int binary_search(int * arr, int element, int start, int end){  //arr에서 element의 인덱스 반환
    int mid = (start+end)/2;
    if(arr[mid]==element)
        return mid;
    else if(arr[mid]<element)
        return binary_search(arr, element, mid+1, end);
    else
        return binary_search(arr, element, start, mid-1);
}

---

문제 풀이

  이번 문제는 입력된 수들을 정렬시키지만, 정렬시키기 전의 순서도 기록을 해야합니다. 따라서 정렬 전을 기록하기 위한 'num' 배열과, 정렬시킨 후를 기록하기 위한 'num_sort' 배열을 만들어 수들을 입력받습니다. 카운팅 정렬을 사용하면 쉬울 것 같은 문제이지만, \(X_i\)의 범위가 너무 넓어 카운팅 정렬을 사용하면 메모리 제한(512MB)이 넘습니다. 또한 시간 복잡도 \(O(n^2)\)의 배열을 사용하면 시간이 초과되므로, \(O(nlogn)\)인 병합 정렬을 사용합니다.

  병합 정렬 자체는 이전 문제들과 동일합니다. 11650번 문제의 소스 코드를 참고하여, 'merge_sort'와 'merge' 함수를 이용해 병합 정렬을 진행합니다. Line 19의 merge_sort(num_sort, 0, N);가 완료되면, num에는 정렬 전 배열이, num_sort에는 정렬 후 배열이 남게 됩니다. 예제와 같이 '2 4 -10 4 -9'가 입력되면 num에는 그대로 저장하고 있고, num_sort는 정렬된 '-10 -9 2 4 4'를 저장하고 있겠죠? 이때 중복되는 숫자들을 제외한다면 인덱스 i는 숫자 num_sort[i] 보다 작은 숫자들의 개수가 되므로, 중복되는 숫자들을 제외한 새로운 배열 'num_order'을 만듭니다 (Line 22 ~ 28). 위의 예제대로라면 num_order는 '-10 -9 2 4'를 저장하게 되고, 예를 들어 4보다 작은 숫자들의 개수를 알고 싶다면 그 인덱스를 참고하여 3개임을 확인할 수 있습니다.

  마지막 과정은 처음에 입력된 num의 숫자들을 변환하는 과정입니다. 변환 과정은 num_order을 참고하여, num_order 내에서 해당 숫자의 인덱스로 바꿔주는 것입니다. 원래 같으면 굉장히 쉬운 과정이지만, 이번에는 시간 제한 때문에 다소 복잡해집니다. 배열 내에서 숫자를 찾는 것은 시간 복잡도 \(O(n)\)을 가지고, num 내의 숫자들을 하나씩 처리하는 과정도 \(O(n)\)이 걸리므로, 단순하게 한다면 \(O(n^2)\)의 시간이 걸려 시간이 초과됩니다. 이 문제를 해결하기 위해 \(O(logn)\) 시간 안에 배열 내 숫자를 찾아주는 함수 'binary_search'를 정의해줍니다 (Line 108~116). Binary Search (이진 탐색)은 정렬된 배열을 재귀적으로 탐색하여 특정한 값의 위치(인덱스)를 찾는 기법입니다. 이때 한 번 재귀적으로 탐색할 때마다 탐색 범위가 절반씩 줄어들기 때문에 앞에서부터 차례로 탐색하는 것보다 훨씬 빠르게 찾을 수 있습니다. 이러한 Binary Search 알고리즘을 이용하면, 해당 문제를 \(O(nlogn)\) 시간 안에 해결할 수 있습니다.

  아래는 백준 웹사이트 "11650번 - 좌표 정렬하기" 문제풀이 링크입니다. 병합 정렬 코드에 대한 더 자세한 설명이 궁금하면 참고해주세요!

[백준/C언어] 11650번 - 좌표 정렬하기