백준 18870번 C++ 풀이

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

18870번: 좌표 압축

 

좌표값이 몇번째에 있는지 출력하는 문제. 특이하게도 이 문제는 정렬하는것이 아닌, 중복을 제거하는 과정에서 애를 먹었다. 컨테이너에서 앞부분에 unique한 원소들로 채워넣고, 뒷부분에는 남은 원소들로 채운다음, 뒷부분의 포인터를 반환하는 unique함수의 동작원리때문에 애먹었다. std::move()함수를 통해 동작하기 때문에, 이를 이해하려고 했는데, 이를 이해하기 위해서는 rvalue, lvalue와 같은 value category에 대해 알아야 한다. 그래서 일단은 값을 옮겨준다! 라고 이해를 하고 넘어가자 (C++ 배운사람들앞에서 이런 소리하면 혼나긴 하겠다만 뭐 어쩔 수 있나).

 

unique함수는 first와 result라는 두개의 포인터가 사용되는데, first는 이름에서 볼 수 있듯이 맨 첫번째 요소를 가르키는 포인터이다. result포인터는 중복이 아닌 원소라고 판단한 경우 값을 대입할 위치를 가르키는 포인터이다. 이때 fisrt포인터가 끝까지 나아가면서, result가 가리키고 있는 값과 first가 가리키고 있는 값이 다르다면 result를 한 칸 옮기고 거기에 first가 가리키는 값을 덮어 씌운다. 문제는, 포인터는 하나의 값만을 가르키기 때문에, 1을 가르켰다가 2를 가르키고, 다시 1을 가르키면 이게 중복인지 아닌지 판단하지 못한다. 그렇기 때문에 unique함수를 제대로 쓰기 위해서는, 정렬를 한번 해줘야 한다.

 

unique는 단순히 중복값을 다 밀어버리는 함수야! 라고 이해를 하고 코드를 짰다가, 중복제거가 전혀 안되서 왜 안되지?? 하고 고민하다가 여기까지 와버렸다. 솔직히 아직 제대로 배우지 않았기 때문에, 설명이 제대로 안됐을 것이다. 그러니 스스로 한번 찾아보길 바란다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, temp; 
    cin >> n;
    vector<int> v; // 원본 좌표
    vector<int> cv; // 정렬하기 위한 좌표
    vector<int>::iterator iter; // 반복자

    for(int i = 0; i < n; i++) { // 입력
        cin >> temp;
        v.push_back(temp);
        cv.push_back(temp);
    }
    
    sort(cv.begin(), cv.end()); // 정렬
    cv.erase(unique(cv.begin(), cv.end()), cv.end()); // 중복제거
    
    for(iter = v.begin(); iter != v.end(); iter++) { // 원본 좌표값을 압축하여 출력
        // 원본좌표값을 정렬한 벡터에서 위치를 찾고, 정렬한 벡터의 시작주소간의 거리를 출력. 
        cout << lower_bound(cv.begin(), cv.end(), *iter) - cv.begin() << ' '; 
    }
}

 

 

참조한 unique 함수의 설명 :

• https://dpdpwl.tistory.com/39 <- 댓글 중 Modin님의 댓글
• https://en.cppreference.com/w/cpp/algorithm/unique