[백준] 18870 - 좌표 압축

문제

18870번: 좌표 압축

해결 과정

처음에는 원래의 배열과 솔트한 배열을 작은 숫자부터 비교해 가며 정답 배열에 순서값을 넣은 후 정답 배열을 출력하는 방법을 이용했다. 

#include <stdio.h>
#include <algorithm>

int main() {
    
    int n;
    scanf("%d", &n);
    
    int num[n], sorted[n], ans[n], cur = 0;
    
    for (int i = 0; i < n; i ++) {
        scanf("%d", num+i);
        sorted[i] = num[i];
    }
    
    std::sort(sorted, sorted + n);
    
    for (int i = 0; i < n; i ++) {
        if (i != 0 && sorted[i] == sorted[i-1])
            continue;
        for (int j = 0; j < n; j ++)
            if (sorted[i] == num[j])
                ans[j] = cur;
        cur ++;
    }
    
    for (int i = 0; i < n; i ++)
        printf("%d ", ans[i]);
    printf("\n");
    
}

 

위 코드는 정상적으로 작동은 하지만 n <= 1000000이면서 O(n^2)이기 때문에 시간 초과가 발생했다. 시간복잡도를 줄일 수 있는 방법을 고민해봤지만 방법이 떠오르지 않았다. 힌트를 얻고자 검색했을 때 아래 글을 발견했다.

 

[백준 알고리즘 18870] 좌표 압축

위의 글에서 내가 써본 적 없는 함수인 unique와 딱 한 번 써본 lower_bound를 이용했다는 것까지 보고 위 문제를 다시 풀게 되었다.

결과

#include <stdio.h>
#include <algorithm>

int main() {
    
    int n;
    scanf("%d", &n);
    
    int num[n], sorted[n];
    
    for (int i = 0; i < n; i ++) {
        scanf("%d", num+i);
        sorted[i] = num[i];
    }
    
    std::sort(sorted, sorted + n);
    int *last = std::unique(sorted, sorted+n);
    
    
    for (int i = 0; i < n; i ++)
        printf("%d ", std::lower_bound(sorted, last, num[i]) - sorted);
    printf("\n");
    
}

메모리는 저렇게 보여도 다른 사람들에 비해 높은 편이 아니었다. 시간이 약간 아쉽다.

회고

우선 STL의 함수들을 한 번 돌아볼 필요가 있다고 느꼈다. STL 함수를 알면 알 수록 능력의 폭이 훨씬 넓어지는 느낌이 든다.

이와는 별개로 주소값을 이용해 답을 낸 것 역시 생각의 폭을 넓혀주었다. 주소값 자체는 쓰레기 값일지 몰라도 주소값의 차는 유용한 값이 될 수 있다는 것을 깨달았다.