[백준 / C++] 18870번 좌표 압축 - map, priority queue, lower bound

백준 18870번 좌표 압축 문제 및 코드 풀이

 

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

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

 

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

예제 입력 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

 

---

 

코드 풀이

 

이 문제를 분석해봤을 때, 일반 구현보다는 STL 함수를 잘 쓸 수 있는 역량을 가지고 있나를 본다는 느낌이 들었다. 

나는 2가지 STL 함수를 이용해서 풀었다.

 

첫번째, Priority queue 

priority queue는 말 그대로 우선순위를 나타낼 수 있는 큐이다. 

#include <queue>

priority_queue<int, vector<int>, greater<int>> pq; // 오름차순
priority_queue<int> pq;  // 내림차순

 

이렇게 2가지 방향으로 설정을 할 수 있고, 이 문제에서는 오름차순을 이용해서 제일 낮은 값이 queue의 first에 나오게끔 이용했다. 그렇게 되면 queue에 pop되는 순서대로 0, 1, 2, 3, 4, 5 ... 등의 압축된 좌표를 나타낼 수 있다.

 

두번째는 map을 이용해 풀었다. 

#include <map>

map<int, int> m; // 첫번째 요소 Key, 두번째 요소 value 값

m.insert({key 값, value});

// 만약, map 안에 값을 찾고 싶다면?
if(m.find(ex) != m.end()){
	// 값이 존재
}
else{
	// 값이 존재 하지 않음
}

// map을 반복해서 출력하고 싶다면?
for(auto i = map.begin(); i != map.end(); i++){
	cout << i->first << " " << i->second << '\n';
}

이유는, 주어진 좌표를 압축하여 나타내는 문제이기 때문에 원래의 좌표와 압축된 좌표를 맵핑해서 해당값(Key)이 호출되면 map에서 key를 넣어 value를 호출하는 식으로 이용했다. 

 

 

이 방식외에 다른 풀이를 찾아보니 lower bound 방식도 사용하는 것을 볼 수 있었다.

lower_bound는 정렬된 값들 사이에서 원하는 값 중 가장 처음인 값의 인덱스를 출력하는 것이다. 

이 방법도 괜찮은 것 같으니 이 2가지 방법 중 원하는 방법을 쓰면 될 것 같다. 

---

 

18870 전체 코드 

#include <iostream>
#include<map>
#include<queue>
using namespace std;

priority_queue<int, vector<int>, greater<int>> pq;
map<int, int> m;
queue<int> que;
int main() {

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int num;

		cin >> num;
		pq.push(num);
		que.push(num);
	}

	
	int kkey = 0;
	for (int i = 0; i < n; i++) {
		int ex = pq.top();
		pq.pop();

		if (m.find(ex) != m.end()) {
			continue;
		}
		else {
			m.insert({ ex,kkey });
			kkey++;
		}
	}

	for (int i = 0; i < n; i++) {
		int num = que.front();
		que.pop();
		//cout << num << " : ";
		cout << m[num] << " ";
	}

	return 0;
}