18870: 좌표 압축

네르기·2022년 9월 2일

정렬

알고리즘

목록 보기

64/76

어떤 문제인가?

정렬 후 유일한 값만 추려내어 순서에 맞춰 출력하게 하는 문제.

시행착오 횟수

3번

1차 시도: TE

2021/08/27 이후로 손댄 적이 없는 문제라, 코드를 통해 의도를 살펴봐야 했다.

#include <stdio.h>
#include <stdlib.h>

int p(int *A, int l, int h) {
    int pv=A[h],i=l-1,j=l,t;
    for(;j<h;j++) {
        if(A[j]<pv) {
            t=A[++i];
            A[i]=A[j];
            A[j]=t;
        }
    }
    t=A[i+1];
    A[i+1]=A[h];
    A[h]=t;
    return i+1;
}

void q(int *A, int l, int h) {
    int pv=0;
    if(l<h) {
        pv=p(A,l,h);
        q(A,l,pv-1);
        q(A,pv+1,h);
    }
}

int main() {
    int *A,*X,i,j,t,k=0,m,N;
    char c=1;
    scanf("%d",&N);
    A=(int*)calloc(4,N);
    X=(int*)calloc(4,N);
    for(i=0;i<N;i++) scanf("%d",&X[i]);
    for(i=0;i<N;i++) {
        c=1;
        for(j=0;j<k;j++) {
            if(A[j]==X[i]) {
                c=0;
                break;
            }
        }
        if(c) A[k++]=X[i];
    }
    q(A,0,k-1);
    for(i=0;i<N;i++) {
        t=0;j=k-1;
        while(1) {
            m=(t+j)/2;
            if(A[m]==X[i]) {
                printf("%d ",m);
                break;
            }
            if(t>=j) break;
            else if(A[m]>X[i]) j=m-1;
            else t=m+1;
        }
    }
}

뭔가 굉장히 복잡하지만, 3줄로 요약할 수 있다.

입력받은 값을 담은 배열 X를 똑같이 복사한 배열을 만들고, 그 배열에 유일한 값 만 담는다. 이 배열을 A라고 칭하자.
A를 퀵소트로 정렬한다.
X의 원소를 가지고 A의 원소를 이진 탐색하여 인덱스를 찾는다.

... 다 좋은데 한가지 결정적인 문제가 있었다. 1번 과정에서 선형 탐색 을 사용했다. 원소가 100만개까지 들어오는데, 여유롭게 2중 반복문이나 썼으니 시간 초과는 피할 수 없었던 셈이다.

2차 시도: TE

그 문제가 있었음을 당시에도 알았던 모양인지, 그 부분을 최대한 최적화하려고 했지만 시간 초과가 났다. 그럼 문제는 둘 중 하나다. 그 당시 구현했던 퀵소트 혹은 이진탐색 알고리즘 둘 중 하나가 성능이 구렸거나, 혹은 둘 다였거나. 직접 만드는게 항상 좋은 건 아니다.

아, 지금 보니 calloc() 매개변수 위치가 서로 뒤바뀌어 있다. 혹시 이게 영향을 준 건 아닐까 의심이 가기는 하는데, 지금에서야 풀었으니 더 이상 신경은 쓰지 않겠다.

3차 시도: AC

stdlib 을 이용해서 최대한 코드를 편하게 썼다. 도구가 있으면 쓸 줄을 알아야지.

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
   int num1 = *(int*)a;
   int num2 = *(int*)b;

   if(num1 > num2)
       return 1;
   if(num1 < num2)
       return -1;
   return 0;
}

int main() {
   int *X, *X2, *X3, N, k=1;
   scanf("%d", &N);

   X = (int*) calloc(N, sizeof(int));
   X2 = (int*) calloc(N, sizeof(int));
   X3 = (int*) calloc(N, sizeof(int));

   for(int i=0;i<N;i++) {
       scanf("%d", &X[i]);
       X2[i] = X[i];
   }
   qsort(X, N, sizeof(int), compare);
   
   X3[0] = X[0];
   for(int i=1;i<N;i++) {
       if(X3[k-1] != X[i])
           X3[k++] = X[i];
   }

   for(int i=0;i<N;i++)
       printf("%d ", ((int *)bsearch(&X2[i], X3, k, sizeof(int), compare) - X3));
}