[C/C++] 좌표 압축 (백준 18870)

문제

 

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

 

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

 

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

 

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

입력

 

5
2 4 -10 4 -9

출력

 

2 3 0 3 1

풀이

 

나름 감회가 새로운 문제입니다. 이때까지 한 1주일 정도 공부하고 간단하게 암기하고 활용했던 코드들을 활용해서 문제를 풀었기 때문입니다.

 

문제를 확실하게 확인하기 위해서 진짜 하라는 대로 코드를 짜보았습니다.

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main(void){

    int n;
    scanf("%d", &n);
    vector<int> v;
    vector<int> v2;

    for(int i = 0 ; i < n ; i++){
        int temp;
        scanf("%d",&temp);
        v.push_back(temp);
    } // 초기화


    for(int i = 0 ; i < n ; i++){
        int cnt = 0;
        for(int j = 0 ; j < n ; j++){
            if(v[i] > v[j]){
                cnt++;
            }
        }
        printf("%d ", cnt);
    }

    return 0;
}

 

두 배열을 만들어서 비교를 해서 자신보다 작은 숫자의 수를 세어서 넣어보았습니다만... 역시나 시간초과가 났습니다. 이제 선형탐색은 최대한 자제해야하는 것 같습니다.

 

그 다음으로는 upper bound와 lower bound를 활용해볼까도 생각해보았습니다만 아무래도 '갯수'에 특화 되어있는지 제 머릿속에서는 어떤식으로 활용할지 도저히 떠오르지가 않았습니다.

 

정답률 60퍼인데 이런 고민을 하고 있는걸 보면 정답률이랑 난이도는 크게 의미가 없는 걸지도...

 

결국 고안해낸 답은 제가 이때까지 배운걸 모조리 섞는 것입니다. 정렬, 중복제거, 이분탐색 이렇게 3가지를 섞어서 코드를 짰습니다.

 

처음에는 정렬로 일단 전체를 정렬하고 중복제거를 통해서 중복을 제거하고 이분 탐색을 통해서 같은 숫자를 찾으면 그 인덱스 값을 답으로써 반환하는 방식으로 활용해보았습니다.

 

코드

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

long n;
vector<long> v;
vector<long> v2;
long answer;

void binary_search_mine(long min, long max, long value){\
    if(min > max) return;
    long middle = (min + max) / 2;

    if(v2[middle] > value){
        binary_search_mine(min, middle-1, value);
    }
    else if(v2[middle] < value){
        binary_search_mine(middle+1, max, value);
    }
    else{
        answer = middle;
    }
}

int main(void){
    scanf("%ld", &n);
    for(long i = 0 ; i < n ; i++){
        long temp;
        scanf("%ld",&temp);
        v.push_back(temp);
    } // 초기화
    v2 = v;
    sort(v2.begin(), v2.end()); //정렬
    v2.erase(unique(v2.begin(), v2.end()), v2.end()); //중복 제거
    long size = v2.size();

    for(long i = 0 ; i < n ; i++){
        binary_search_mine(0, size, v[i]);
        printf("%d ", answer);
    }
    return 0;
}