[S2] 18870. 좌표 압축

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

18870번: 좌표 압축

보니까 좌표압축이라는 알고리즘이 존재했다. 그래서 한번 검색을 해서 찾아봤는데, 이상하게 내가 푼 방식이 더 효율적이라 생각한다. 

그래서 내가 푼 방식과 원래 이 알고리즘을 해결하는 방식 이렇게 2가지를 소개하려 한다.

이 문제는 하나의 배열을 이용하여 단순 정렬하기에는 어렵다. 하나의 배열을 이용한다면 3번의 정렬이 필요하기 때문이다. - 그래도 되려나? 모르겠다 ㅋㅋ

왜냐하면 원래의 순서대로 정렬된 값을 출력해야 하기 때문이다. 다시 원상복구 시키고 출력하는데 시간이 꽤 걸릴것이라 예상된다.

 

방법 1. 

unique함수 사용. algorithm라이브러리에 존재하는 unique함수를 사용하는 것이다.

자. 우리는 주어진 값의 정렬된 값들의 index를 알고 싶은 것이다. 그러니까 입력으로 2 4 -10 4 -9가 있다고 하자.

그러면 -10 -9 2 4로 정렬한 뒤, 2는 2번째, 4는 3번째, -10은 1번째, -9는 2번째이기 때문에 순서대로 2 3 0 3 1이 출력되어야 답이 나오게 된다. 그렇기 때문에 우리는  2 4 -10 4 -9를 정렬을 하되, 중복되는 값들은 제거해야 한다. 

 

나도 여기까지는 생각을 했었다. 중복되는 값을 제거해보자 라는 생각을 했지만, 제한에서 X의 값은 -10^9 ~ 10^9였다. bool변수를 활용하여 중복을 없애기에는 너무 범위가 컸다. 여기에서 활용되는 것이 erase와 같이 활용되는 unique함수이다.

unique함수는 다음 글에서 자세하게 다룬다.

간단하게 말하면 unique함수는 중복되는 값들을 삭제해준다. 그리고, 삭제를 하여 완성된 배열의 가장 뒷 부분의 iterator를 반환해준다. 자세한 내용은 아래 글을 참고하자.

https://jhcard.tistory.com/13

[C++] algorithm 라이브러리

unique의 개념을 알았기 때문에 이제 erase와의 결합을 생각해야 한다. erase와의 결합도 위의 글에 나와있지만, 다시 한번 말해보면 erase함수는v.erase(Siterator, Eiterator)를 이용하여 Siterator~Eiterator사이의 값을 전부 삭제가 가능하다. 그렇기 때문에 v.erase(std::unique(v.begin(), v.end()), v.end())로 중복된 값이 제거된다. 

 

자 이제 우리는 중복되지 않은 정렬된 값을 얻게 되었다. 

이제 원래 입력된 좌표값을 활용하여 해당 숫자가 몇번째 index에 있는지만 알아내면 된다. 해당 값은 algorithm라이브러리에 있는 lower_bound함수를 활용하려고 한다. 해당 내용도 위의 포스팅을 참고하자.

 

코드는 다음과 같이 나온다.

#include <cstdio>
#include <vector>
#include <algorithm>

int main(void) {
    int N, num, X[1000000]; scanf("%d", &N);
    std::vector<int> v;
    for (int i = 0; i < N; i++) {
        scanf("%d", &X[i]);
        v.push_back(X[i]);
    }

    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());

    for (int i = 0; i < N; i++) {
        printf("%d ", std::lower_bound(v.begin(), v.end(), X[i]) - v.begin());
    }
}

 

방법 2.

rank? 를 이용한 정렬을 사용했다고 보면 된다. 

보면 위의 방법은 O(nlogn)을 2번 사용, O(n)을 1번 사용했다고 봐도 된다. sort - O(nlogn), unique - O(n), lower_bound * n- O(nlogn)

하지만, 이 방법은 정렬 1번, O(n)탐색 2번을 하는 방법이다. 대신에 메모리를 많이 차지하게 된다. 배열을 3개 사용해야 되기 때문이다. 위의 방식도 배열을 2개 사용하기는 했다. 이 차이가 있다.

 

자. 약간 이해하기 어려울 수 있다.

3개의 배열의 의미를 먼저 알아보자.

A  - 입력된 배열

L - 우선 index의 값이 저장된다. 하지만, A에 의해 재정렬 된다. 이 정렬된 값을 이용하여 R배열에 저장하게 된다.

R - 정답을 출력하기 위한 배열

 

가장 중요한 코드를 보여주겠다.

std::sort(L, L + N, [&A](int a, int b){return A[a] < A[b];});

자

우선 L배열에는 0 ~ N까지의 값이 순서대로 저장되어 있다. 보면 sort를 L배열로 하는데 비교하여 return 하는 값이 A[a] < A[b]이다. A기준으로 L을 정렬 하는 것이다. 

A = {2, 4, -10, 4, -9} 를 예로 들어보자. 처음에는 L 배열은 

L = {0, 1, 2, 3, 4} 로 저장되어 있다. 

위의 sort문을 실행시켜 보자.

L = {2, 4, 0, 1, 3}이 저장될 것이다. 

sort의 a, b에는 L에 저장되어 있는 값이 들어가게 되고, 이것을 비교하게 될것이다. 만약  a에 2, b에 4가 들어갔다 하자. 

그러면 A[2] < A[4] 는 -10 < -9로 참이기 때문에 -10이 왼쪽으로, -9가 오른쪽으로 가게 될 것이다. 

이해가 되는가?

 

그러면 우리는 위의 정렬을 통해 새롭게 정렬된 L배열을 얻게 되었다.

이제 우리는 중복되는 값을 제거시키면 된다. 그것은 다음을 사용하면 된다.

A[L[i]] 와 A[L[i+1]]의 값이 동일하다면 순위를 하나 증가할 필요가 없다. 그러니까 우리는 L에 저장되어 있는 순서대로 A를 방문하고, 그 값을 R에 저장하면 되는 것이다.

R[L[0]] = 0;
for (int i = 1; i < N; i++) {
    if (A[L[i - 1]] == A[L[i]]) R[L[i]] = R[L[i - 1]];
    else R[L[i]] = R[L[i - 1]] + 1;
}

해당 코드를 실행하면 되는 것이다. 

전체 코드는 다음과 같다.

#include <cstdio>
#include <utility>
#include <algorithm>

int main(void) {
    int N, L[1000000], A[1000000], R[1000000]; scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
        L[i] = i;
    }

    std::sort(L, L + N, [&A](int a, int b){return A[a] < A[b];});
    R[L[0]] = 0;
    for (int i = 1; i < N; i++) {
        if (A[L[i - 1]] == A[L[i]]) R[L[i]] = R[L[i - 1]];
        else R[L[i]] = R[L[i - 1]] + 1;
    }
    for (int i = 0; i < N; i++) printf("%d ", R[i]); 
}