[C++] 백준 18870 - 좌표 압축

• 풀이 방법

• 초기코드 (실패)

• 최종 코드

 

풀이 방법

처음에는 시간 제한과 입력크기를 고려했을 때, N^2으로 해도 괜찮을 줄 알았다. 그래서 배열로 받아서 크기순으로 정렬하고, 중복값은 무시하도록 처리했다. 그 후 좌표 검색할 때는 선형으로 N^2으로 구현하였다.

 

초기코드 (실패)

#include <iostream>
#include <cstring>

int N;
int arr[1000000];
int result[1000000];

int main(void){
    scanf("%d", &N);
    
    for(int i=0; i<N; i++){
        scanf("%d", &arr[i]);
    }
    
    for(int i=0; i<N; i++){
        int tmp[1000000];
        memset(tmp, 0, 1000000);
        int cnt = 0;
        for(int j=0; j<N; j++){
            if(i==j)
                continue;
            
            if(arr[i]>arr[j]){
                int k = 0;
                for(; k<cnt; k++){
                    if(arr[j] == tmp[k]){
                        break;
                    }
                }
                if(k == cnt){
                    result[i]++;
                    tmp[cnt++] = arr[j];
                }
            }
        }
    }
    
    for(int i=0; i<N; i++){
        printf("%d ", result[i]);
    }
    
}

해당 코드는 시간 초과가 발생하였다.
역시 N^2으로 구현하면 안되겠다는 생각이 들어 마지막에 탐색할 때 이진탐색으로 바꿨다. 그리고 성공했다.

 

최종 코드

#include <iostream>
#include <cstring>
#include <algorithm>

#define MAX 1000000
using namespace std;

int N;
int arr[MAX];
int result[MAX];
int sorted[MAX];
int fin[MAX];
int cnt;

void bs(int x, int y, int point){
    int mid = (y-x)/2;
    
    mid += x;
    
    if(result[mid] == arr[point]){
        fin[point] = mid;
        return;
    }
    else if(result[mid]>arr[point]){
        bs(x, mid-1, point);
    }else{
        bs(mid+1, y, point);
    }
    
}

int main(void){
    scanf("%d", &N);
    
    for(int i=0; i<N; i++){
        scanf("%d", &arr[i]);
        sorted[i] = arr[i];
    }
    
    sort(sorted, sorted+N);
    result[0] = sorted[0];
    
    int count = 1;
    for(int i=1; i<N; i++){
        if(sorted[i] == sorted[i-1])
            continue;
        result[count++] = sorted[i];
    }
    
    for(int i=0; i<N; i++){
        cnt = 0;
        bs(0, count-1, i);
    }
    
    for(int i=0; i<N; i++){
        printf("%d ", fin[i]);
    }
    
}

 

다른 사람들의 풀이를 보니 unique, erase 함수와 lower_bound를 사용했다. 아직 STL 사용이 익숙치 않아서 손수 다 구현했다. 물론 이렇게 하면 더 low하게 이해할 수 있지만 장기적으로 봤을 때는 효율적이진 않다. 이제 학습했으니 다음부턴 적극 사용해야겠다.