[백준]_18870번 : 좌표 압축(파이썬 and C언어)

18870번: 좌표 압축

단순해 보이는 문제이지만 자칫하면 시간 초과나 메모리 초과로 이어질 수 있는 문제이다. 일단 파이썬으로는 어떤 방식으로 접근해야 하는지 생각해 보자. 

---

전략(Python)

예시 입력들을 보아하니 원소 a보다 작은 숫자의 종류가 몇개인지 구하는 것임을 알 수 있다. 즉 중복을 제외하고 세어야 하는 것이다. 하지만 동시에 출력을 위해서는 중복을 제거하지 않은 리스트를 통해서 해야 한다. 그래서 다음과 같은 생각을 할 수 있다.

 

1. 먼저 우리가 사용할 자료들을 전부 만들어 준다.

import sys
input=sys.stdin.readline
n=int(input()) # 리스트의 길이
ls=list(map(int, input().split()[:n])) # 리스트 입력
arr=sorted(list(set(ls))) # 중복을 제거한 리스트

2. 중복을 제거하고 오름차순으로 정렬한 리스트 arr를 생각해보자. 만약 예제 입력 1과 같이 2,4,-10,4,-9를 입력했으면 arr에는 -10,-9,2,4로 저장되었을 것이다. 여기서 각 숫자들의 인덱스를 관찰하면 흥미로운 사실을 발견할 수 있다. 그것은 바로 (arr에서의 인덱스)는 좌표 압축에서 구하는 답과 같다는 사실이다!! 숫자가 클수록 arr에서 인덱스가 뒤로 밀리고 앞에 존재하는 자신보다 작은 숫자들의 개수가 결국 인덱스에 반영되는 것이다. 하지만 이것을 아래와 같이 짜면 시간 초과가 발생한다.

for el in ls: print(arr.index(el), end=' ')

 왜냐하면 arr.index(el)은 el이 arr 어디에 있는지 arr 전체를 검사해야 하기 때문에 시간이 오래 걸린다. 따라서 아래와 같이 먼저 인덱스(답)을 사전으로 옮겨주고 나서 출력을 하는 방법을 택해야 한다.

com_dic={arr[i] : i for i in range(len(arr))}
for el in ls:
    print(com_dic[el], end=' ')

따라서 최종 코드는 다음과 같다.

시도 1(Python)

import sys
input=sys.stdin.readline
n=int(input())
ls=list(map(int, input().split()[:n]))
arr=sorted(list(set(ls)))
com_dic={arr[i] : i for i in range(len(arr))}
for el in ls:
    print(com_dic[el], end=' ')

---

전략(C언어)

이제 C언어로는 어떻게 짜야할지 생각해보자. 사실 위의 파이썬과 논리의 흐름은 다르지 않다. 아래와 같은 과정을 거쳐주되 한 땀 한 땀 자신이 짜야한다는 수고를 거쳐야 한다.

1. 배열 A의 크기를 입력받는다. 이때 calloc(malloc도 좋다)으로 동적배열을 선언해 준다.
2. 배열에 들어갈 요소들을 하나하나 입력받는다. 이때 다른 배열 B(오름차순 정렬, 중복 삭제를 거칠 배열)에도 똑같이 값을 넣어준다. 왜냐하면 우리는 답을 출력하기 위해 기존 배열을 보존해야 하기 때문이다.
3. qsort를 통해 배열 B를 오름차순으로 만들어주고  배열B를 중복 제거 함수를 통해 정리함과 동시에 새로 정리된 배열 B의 길이를 변수에 저장해준다. 
4. 배열 B의 길이를 왜 저장했나 싶겠지만 이제 우리는 배열A에 존재하는 요소가 배열B 어디에 위치해 있는지 알아내야 한다. 따라서 이분 탐색을 사용해야 한다(이분 탐색을 사용할 수 있는 이유도 배열 B가 이미 오름차순이기 때문이다). 
5. 배열 B, 배열 A 원소, 배열 B의 길이를 인자로 이분 탐색 함수로 전달해 준다. 
6. 이분탐색을 통해 찾은 배열 B에서 찾은 배열 A 원소의 인덱스를 차례대로 출력한다.  

시도 2(C언어)

#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b){
    return *(int*)a-*(int*)b;
}
int binary_search(int* arr, int target, int size) // 인덱스 추출
{
    int start=0;
    int end=size-1;
    int mid;
    while(start<=end)
    {
        mid=(start+end)/2;
        if (arr[mid]==target)
            return mid;
        else if(arr[mid]>target)
            end=mid-1;
        else
            start=mid+1;
    }
}
int unique(int* arr, int size) {
    int i, j = 0;
    for (i = 1; i < size;i++) {
        if (arr[j] == arr[i]) continue;
        arr[++j] = arr[i];
    }
    return ++j;
}
int main(){
    int size;
    scanf("%d",&size);
    int* arr=(int*) calloc(size,sizeof(int));
    int* sorted=(int*) calloc(size,sizeof(int));
    for (int i = 0; i < size; ++i) {
        scanf("%d",&arr[i]);
        sorted[i]=arr[i];
    }
    qsort(sorted, size, sizeof(int), compare);
    int cnt=unique(sorted, size);
    for (int i = 0; i < size; ++i) {
        printf("%d ",binary_search(sorted, arr[i], cnt));
    }

    free(arr);
    free(sorted);
    return 0;
}