C - [백준 18870] 좌표 압축 (feat. 이분탐색, 퀵정렬)

2025.02.03 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 이분 탐색 (Binary Search)

[자료구조 & 알고리즘] 이분 탐색 (Binary Search)

 

2025.02.03 - [Computer Science/알고리즘 문제] - ★ C - [백준 2295] 세 수의 합 (feat. 이분탐색)

 

 

 

 

https://www.acmicpc.net/problem/18870

---

좌표 압축 문제 풀이 (백준 18870번)

이번 포스트에서는 백준 18870번 좌표 압축 문제를 C언어로 풀이하는 방법을 알아보겠습니다. 이 문제는 대규모 입력 데이터를 효율적으로 처리하기 위해 정렬과 이진 탐색을 활용하는 것이 핵심입니다.

---

문제 설명

N개의 좌표가 주어졌을 때, 각 좌표를 압축된 값으로 변환하는 프로그램을 작성해야 합니다. 압축된 좌표는 다음과 같은 방식으로 정의됩니다:

1. 주어진 좌표들을 크기 순서대로 정렬하고, 중복된 값을 제거합니다.
2. 정렬된 좌표들에 대해 각 좌표가 몇 번째로 작은 값인지 인덱스로 변환합니다.

---

입력 및 출력 형식

• 입력:
  • 첫째 줄에 좌표의 개수 N이 주어집니다. (1 ≤ N ≤ 1,000,000)
  • 둘째 줄에 N개의 정수가 공백으로 구분되어 주어집니다.
• 출력:
  • N개의 좌표를 압축된 값으로 출력합니다.

---

Checkpoint

예제를 보고 문제의 컨셉을 쉽게 획득할 수 있던 문제이다.

입력값을 중복값 없이 오름차순으로 나열하여 압축 번호 배열을 생성하면 

특정 숫자의 압축 번호가 압축 번호 배열 인덱스 번호가 된다.

 

문제 풀이 접근

1. 입력값 복사 및 정렬
   원본 배열과 복사본을 만들어 정렬 후 중복을 제거합니다.
2. 좌표 압축
   중복 제거된 배열에서 이진 탐색을 사용하여 각 좌표가 정렬된 배열에서 몇 번째인지 찾아 출력합니다.

---

C언어 코드

/*
C_BOJ_18870_좌표압축
https://www.acmicpc.net/problem/18870
*/

#include 
#include 
#define MAX 1000000

int arry[MAX] = {0};
int unique[MAX] = {0};
int copy[MAX] = {0};

int compare(const void *a, const void *b) {
    int int_a = *(const int *)a;
    int int_b = *(const int *)b;

    if (int_a > int_b) return 1;
    if (int_a < int_b) return -1;
    return 0;
}

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

    // 좌표 입력 받기
    for (int i = 0; i < N; i++) {
        scanf("%d", &arry[i]);
    }

    // 원본 배열 복사
    for (int i = 0; i < N; i++) {
        copy[i] = arry[i];
    }

    // 좌표 정렬
    qsort(arry, N, sizeof(int), compare);

    // 중복 제거 및 압축 좌표 배열 생성
    int index = 0;
    unique[index++] = arry[0];
    for (int i = 1; i < N; i++) {
        if (arry[i] != arry[i - 1]) {
            unique[index++] = arry[i];
        }
    }

    // 이진 탐색으로 각 좌표의 압축 값 출력
    for (int i = 0; i < N; i++) {
        int target = copy[i];
        int start = 0;
        int end = index - 1;

        // 이진 탐색 시작
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (target == unique[mid]) {
                printf("%d ", mid);
                break;
            } else if (target < unique[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
    }

    return 0;
}

---

코드 설명

 

1. 입력 및 배열 복사
   • 좌표값을 arry 배열에 입력받습니다.
   • 이후 원본 데이터를 유지하기 위해 copy 배열에 복사합니다.

for (int i = 0; i < N; i++) {
    scanf("%d", &arry[i]);
    copy[i] = arry[i];
}

1. 정렬 및 중복 제거
   • qsort() 함수를 사용하여 arry 배열을 오름차순으로 정렬합니다.
   • 정렬된 배열에서 중복 값을 제거한 후 unique 배열에 저장합니다.

qsort(arry, N, sizeof(int), compare);

unique[index++] = arry[0];
for (int i = 1; i < N; i++) {
    if (arry[i] != arry[i - 1]) {
        unique[index++] = arry[i];
    }
}

1. 이진 탐색 및 출력
   • 각 좌표값에 대해 unique 배열에서 이진 탐색을 수행합니다.
   • 이진 탐색 결과로 해당 좌표의 압축값을 출력합니다.
     • unique[mid]가 target과 같으면 해당 인덱스를 출력합니다.
     • 값이 더 작거나 크면 탐색 범위를 조정하며 반복합니다.

int start = 0, end = index - 1;

while (start <= end) {
    int mid = (start + end) / 2;
    if (unique[mid] == target) {
        printf("%d ", mid);
        break;
    } else if (unique[mid] > target) {
        end = mid - 1;
    } else {
        start = mid + 1;
    }
}

---

시간 복잡도 분석

• 정렬: O(Nlog⁡N)
• 중복 제거: O(N)
• 이진 탐색: O(Nlog⁡N)

전체 시간 복잡도는 O(Nlog⁡N)으로, 최대 N = 1,000,000까지 효율적으로 처리할 수 있습니다.

---

결과 예시

입력:

5
2 4 -10 4 -9

출력:

2 3 0 3 1

---

마무리

이 문제는 대규모 입력 데이터를 효율적으로 처리하는 방법을 배우기 좋은 예제입니다. 특히, 정렬 후 중복 제거와 이진 탐색을 활용하여 시간 복잡도를 줄이는 기법이 중요한 포인트입니다.
C언어로 문제를 풀 때는 qsort() 함수와 이진 탐색 루프를 적절히 사용하는 것이 관건입니다.