[백준/C++] 18870번: 좌표 압축 - STL의 정교한 활용

1. 문제 정보

• 문제 번호: 18870번
• 문제 이름: 좌표 압축
• 문제 요약: 수직선 위의 N개 좌표에 좌표 압축을 적용한다. X_i를 좌표 압축한 결과는 X_i > X_j를 만족하는 서로 다른 좌표 X_j의 개수와 같아야 한다.

2. 문제풀이 과정

값의 크기가 아니라 값의 위치가 중요하기 때문에, find 함수를 썼지만 find함수의 선형탐색 특징 때문에 시간 초과가 발생했다.

해결방법: 정렬된 상태에서 이진 탐색을 수행하는 lower_bound를 사용하면 입력값이 커도 적은 연산으로 수행할 수 있다.

 

**lower_bound는 왜 lower_bound라는 이름을 가지고 있을까??
lower_bound는 하한선이라는 뜻이다. 
그래서!! "내가 찾는 값 X 가 나타나는 가장 첫 번째(가장 낮은 위치)"를 찾기 때문에 붙여진 이름이다.

 

예시: 

{1, 2, 3, 3, 3, 4, 6}에서 3을 찾는다면:

• lower_bound는 첫 번째 3의 위치를 알려준다. (3이 시작되는 하한선)
• upper_bound는 4의 위치를 알려준다. (3이 끝난 바로 다음 상한선)

 

 

 

3. unique와 erase 문법의 정체

C++ STL의 unique는 이름과 달리 요소를 실제로 지우지 않는다. 이 부분이 가장 헷갈리는 포인트이다.

① std::unique(first, last)

이 함수는 연속된 중복 원소를 뒤로 밀어버리고, 중복되지 않은 원소들이 끝나는 지점의 다음 이터레이터를 반환한다.

• 예: {1, 2, 2, 3, 3, 4} → {1, 2, 3, 4, (쓰레기 값), (쓰레기 값)}
• 이때 반환값은 첫 번째 '쓰레기 값'의 위치이다.

② v.erase(unique_it, v.end())

unique가 반환한 이터레이터부터 벡터의 실제 끝(v.end())까지를 삭제하여 물리적으로 크기를 줄인다.

결론: v.erase(unique(v.begin(), v.end()), v.end()); 이 한 줄은 정렬된 벡터에서 중복을 완전히 제거하는 공식과도 같은 문법이다.

 

4. 코드 구현

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

using namespace std;

int main() {
    // 입출력 최적화
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<long long> v(N);
    vector<long long> sorted_v;

    for (int i = 0; i < N; i++) {
        cin >> v[i];
        sorted_v.push_back(v[i]);
    }

    // 1. 정렬
    sort(sorted_v.begin(), sorted_v.end());

    // 2. 중복 제거 (unique + erase 공식)
    sorted_v.erase(unique(sorted_v.begin(), sorted_v.end()), sorted_v.end());

    // 3. 각 원소의 인덱스 찾기 (lower_bound)
    for (int i = 0; i < N; i++) {
        // lower_bound는 이터레이터를 반환하므로 begin()을 빼서 인덱스로 변환한다.
        int idx = lower_bound(sorted_v.begin(), sorted_v.end(), v[i]) - sorted_v.begin();
        cout << idx << " ";
    }

    return 0;
}

 

 

5. 배운 점 & 회고 (TIL)

① lower_bound와 이터레이터 연산

std::lower_bound가 반환하는 값은 단순한 정수가 아니라 해당 위치를 가리키는 이터레이터(Iterator)이다. 이터레이터끼리의 뺄셈(it - v.begin())을 통해 해당 원소가 몇 번째 인덱스인지를 O(1)만에 계산할 수 있음을 배웠다.

② set과 distance의 함정

중복 제거를 위해 std::set을 쓸 수도 있지만, set의 이터레이터는 양방향 이터레이터(Bidirectional Iterator)이다. 따라서 두 이터레이터 사이의 거리를 구하는 std::distance를 쓰면 내부적으로 하나씩 세며 이동하므로 O(N)이 걸린다. 결국 정렬된 벡터 + lower_bound 조합이 가장 빠르고 정석적인 방법이다.

**양방향 이터레이터란?
이터레이터(Iterator)는 포인터처럼 컨테이너의 원소를 가리키는 도구인데, 컨테이너의 구조에 따라 "움직일 수 있는 능력"이 다르다.

1 - 양방향 이터레이터 (예: std::list, std::map, std::set)

말 그대로 앞(++)과 뒤(--)로만 한 칸씩 움직일 수 있는 이터레이터이다.

• 장점: 뒤로 돌아갈 수 있다.
• 단점: "여기서 10번째 칸으로 바로 점프해!"가 안 된다. 10번을 ++ 해서 가야 한다.

2 -  임의 접근 이터레이터 (Random Access Iterator) (예: std::vector, std::deque)

포인터와 똑같은 능력을 가졌다. ++, --는 물론이고 it + 5나 it[3]처럼 한 번에 멀리 점프할 수 있다.

 

③ 효율적인 중복 제거 프로세스

unique 함수가 요소를 물리적으로 지우는 것이 아니라 뒤로 보내기만 한다는 점이 흥미롭다. 반환된 이터레이터를 erase의 시작점으로 활용하는 유기적인 문법 구조를 확실히 익히게 되었다.

④ 시간 복잡도의 중요성

N이 1,000,000일 때 O(N^2)은 불가능하며, 반드시 O(N log N)이하의 알고리즘을 설계해야 한다. 이번 문제는 정렬(O(N log N))과 N번의 이진 탐색(O(N log N))으로 문제를 해결한 전형적인 사례이다.