[BOJ-18870] 좌표 압축

문제

수직선 위에 $N$ 개의 좌표 $X_{1}, X_{2}, ..., X_{N}$이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

$X_{i}$를 좌표 압축한 결과 $X'_{i}$의 값은 $X_{i} > X_{j}$를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

$X_{1}, X_{2}, ..., X_{N}$에 좌표 압축을 적용한 결과 $X'_{1}, X'_{2}, ..., X'_{N}$를 출력해보자.

 

입력

첫째 줄에 $N$이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 $X_{1}, X_{2}, ..., X_{N}$이 주어진다.

 

출력

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

 

제한

• $1 ≤ N ≤ 1,000,000$
• $-10^{9} ≤ X_{i} ≤ 10^{9}$

 

예제 입력 1 

5
2 4 -10 4 -9

 

예제 출력 1 

2 3 0 3 1

 

예제 입력 2 

6
1000 999 1000 999 1000 999

 

예제 출력 2 

1 0 1 0 1 0

 

알고리즘 분류

• 정렬
• 값 / 좌표 압축

 

문제 출처

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

18870번: 좌표 압축

 

---

 

문제 해결 방법

• 생각 보다 쉽지 않았던 문제였다.
• 맨 처음에는 집합(set)과 벡터(vector) 컨테이너를 이용하여 문제를 해결하려고 하였으나 시간 초과로 인해 문제를 해결할 수 없었다.
  • 집합(set) 컨테이너에는 중복되는 원소가 있을 수 없다. 
  • 따라서, 입력 받은 수들을 벡터에 넣는 동시에 집합에 넣은 후 2중 for 문을 이용하여 벡터와 집합의 요소를 비교하는 방법을 사용하였다.
• 그래서 unique() 함수와 lower_bound() 함수를 이용한 방법으로 문제를 해결할 수 있었다.
  • unique() 함수를 사용할 때 주의할 점은 사용 전 컨테이너가 반드시 정렬되어 있어야 하고, 중복 제거 후, 뒷 부분에 원본값이 남게된다는 것이다.
  • lower_bound() 함수를 이용하여 입력받은 값들이 중복이 제거된 uNums 벡터안에 처음으로 등장하는 인덱스 위치를 하나 하나씩 출력하도록 하였다.

sort(uNums.begin(), uNums.end());
uNums.erase(unique(uNums.begin(), uNums.end()), uNums.end());

for (auto i : nums) {
    auto it = lower_bound(uNums.begin(), uNums.end(), i);
    cout << it - uNums.begin() << ' ';
}

 

nums

2

4

-10

4

-9

uNums

-10

-9

2

4

 

• 첫 번째로, nums[0]의 요소 2 이상인 수가 uNums 벡터에서 2번째 인덱스에 처음 등장하므로 2를 출력시킨다.
• 두 번째로, nums[1]의 요소 4 이상인 수가 uNums 벡터에서 3번째 인덱스에 처음 등장하므로 3를 출력시킨다.
• 세 번째로, nums[2]의 요소 -10 이상인 수가 uNums 벡터에서 0번째 인덱스에 처음 등장하므로 0을 출력시킨다.
• 네 번째로, nums[3]의 요소 4이상인 수가 uNums 벡터에서 3번째 인덱스에 처음 등장하므로 3을 출력시킨다.
• 마지막으로, nums[4]의 요소 -9 이상인 수가 uNums 벡터에서 1번째 인덱스에 처음 등장하므로 1을 출력시킨다.

 

코드

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

int N, num;
vector<int> nums, uNums;

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

    cin >> N;
    
    for (int i = 0; i < N; i++) {
        cin >> num;
        nums.push_back(num);
        uNums.push_back(num);     
    }

    sort(uNums.begin(), uNums.end());
    uNums.erase(unique(uNums.begin(), uNums.end()), uNums.end());

    for (auto i : nums) {
        auto it = lower_bound(uNums.begin(), uNums.end(), i);
        cout << it - uNums.begin() << ' ';
    }

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [정렬]
• 실버II

 

unique()

형식

unique(ForwardIterator first, ForwardIterator last)

• 벡터(vector) 컨테이너에서 연속으로 중복된 요소를 제거하는 함수이다.
  • 컨테이너에서 중복되지 않는 원소들을 앞에서부터 채워나가는 함수이며, 남은 뒷부분에는 원본값들이 존재한다.
  • 따라서 erase() 함수와 함께 사용하여 중복 제거 후 남은 부분을 없애준다.
• 사용 전, 반드시 컨테이너가 정렬되어 있어야 한다.
• 사용하려면 <algorithm> 헤더를 불러와야 한다.

 

작동 과정

• 다음과 같이 정렬된 벡터 V가 있다.

1

2

2

3

4

4

5

 

• 다음과 같이 unique() 함수를 사용하면, 연속으로 중복되는 값 2, 4를 없앤다.

unique(V.begin(), V.end());

1

2

2

3

4

4

5

 

• 그리고 남은 부분은 원본값(4, 5)을 유지시켜 준다.

1

2

3

4

5

4

5

 

• unique() 함수는 원본이 유지된 요소들의 첫번째 주소값을 반환한다.

1

2

3

4

5

4

5

 

• 따라서 erase() 함수를 사용하여 원본이 유지된 요소들을 지워준다. (그렇지 않으면 중복 되지 않은 값들을 얻을 수 있다.)

V.erase(unique(V.begin(), V.end()), V.end());

 

• 최종적으로 벡터 V에는 중복이 제거된 요소들만 남게된다.

1

2

3

4

5

 

lower_bound()

형식

lower_bound(ForwardIterator first, ForwardIterator last, const T& val)

• 이진 탐색(Binary Search)으로 원소를 탐색하는 함수
• 찾으려는 키 값보다 크거나 같은(이상, ≥) 숫자가 컨테이너에서 처음 등장하는 주소를 Iterator 형으로 반환한다.
• 탐색을 진행할 컨테이너는 반드시 오름차순으로 정렬되어 있어야 한다.
• 사용하려면 <algorithm> 헤더를 불러와야 한다.

 

사용 예

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

vector<int> V = { 1, 2, 3, 4, 5, 6, 7, 8 ,9 };

int main() {
    cout << "lower_bound(6) : " << lower_bound(V.begin(), V.end(), 6) - V.begin() << endl;

    return 0;
}

lower_bound(6) : 5

• 벡터 V에서 6 이상의 숫자가 처음으로 나오는 위치(6)의 인덱스 번호는 5이다.
• lower_bound() 함수의 반환형은 Iterator로, 실제로 몇 번째 인덱스인지 확인하려면 lower_bound() 값에서 벡터의 첫 번째 주소의 위치값(V.begin())을 빼주면 된다.
  • 그렇지 않을 경우 컴파일 에러가 발생한다.

 

upper_bound()

형식

upper_bound(ForwardIterator first, ForwardIterator last, const T& val)

• 이진 탐색(Binary Search)으로 원소를 탐색하는 함수
• 찾으려는 키 값을 초과(>)하는 숫자가 컨테이너에서 처음 등장하는 주소를 Iterator 형으로 반환한다.
• 탐색을 진행할 컨테이너는 반드시 오름차순으로 정렬되어 있어야 한다.
• 사용하려면 <algorithm> 헤더를 불러와야 한다.

 

사용 예

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

vector<int> V = { 1, 2, 3, 4, 5, 6, 7, 8 ,9 };

int main() {
    cout << "upper_bound(7) : " << upper_bound(V.begin(), V.end(), 7) - V.begin() << endl;

    return 0;
}

upper_bound(7) : 7

• 벡터 V에서 7을 초과하는 숫자(8)가 처음으로 나오는 위치의 인덱스 번호는 7이다. 
• upper_bound() 함수의 반환형은 Iterator로, 실제로 몇 번째 인덱스인지 확인하려면 upper_bound() 값에서 벡터의 첫 번째 주소의 위치값(V.begin())을 빼주면 된다.
  • 그렇지 않을 경우 컴파일 에러가 발생한다.

 

참고 사이트

• https://chanhuiseok.github.io/posts/algo-55/
• https://donggoolosori.github.io/2020/09/26/boj-18870/