[BaekJoon/백준] 18870번 C++

문제 이해하는데만 30분 쓴 것 같다.

어려웠다.

 

문제가 무슨 말인지 도저히 알 수가 없어서 검색을 통해 사람들의 설명을 보고 해결했다.

대충 설명에 대한 메모는 이렇다.

일단 좌표압축이라는 건 조금 생소한 애기였다.

 

좌표를 압축한다 : 해당 좌표의 값을 그 값보다 작은 좌표값들의 개수로 대체한다의 의미

 

예제에 2 4 -10 4 -9가 주어졌는데

리스트의 각 숫자가 자신보다 작은 값들의 갯수로 나타내보면 예제의 정답과 같다.

따라서 이를 표현하기 위해

 

1. 값들을 오름차순으로 정렬

2. 중복을 제거 (메모의 unique와 erase부분. unique는 리턴값으로 '중복처리로 뒤로 미룬 첫번째 위치'를 반환한다. ex 3의 위치)

3. 이 때 값들의 index값이 문제에서 요구하는 정답.

 

하지만 이미 입력값을 오름차순으로 정렬해놓았기에,

입력에서 주어진 순서로 주어진 값의 index 값을 출력해줘야했다.

 

따라서 벡터를 두개로 뒀고

두 벡터에 동일하게 입력값을 넣어주고 하나의 벡터만 정렬한 뒤 중복을 제거해주었고

lower_bound를 통해 이진탐색을 진행하여 인덱스 값을 출력해주었다.

 

lower_bound : 이진탐색기반. 해당하는 값보다 크거나 같은값이 제일 처음 등장하는 곳 위치를 리턴. (정렬 전제)

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

using namespace std;

int main() {
    
    vector<int> v, back;
    int N, input;
    
    cin >> N;
    
    for(int i = 0; i < N; i++) {
        cin >> input;
        v.push_back(input);
        back.push_back(input);
    }
    
    
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    
    for(int i = 0; i < N; i++) {
        printf("%d ", lower_bound(v.begin(), v.end(), back[i]) - v.begin());
    }
    
}

 

+ 처음엔 벡터 대신 set을 사용하려했는데,

set의 lower_bound - set.begin() 을 통한 인덱스 값 도출이 되지 않고 오류만 떠서 애먹다가.. 결국 벡터로했다.