백준 18870번 좌표 압축(C++) (lower_bound)

18870번: 좌표 압축

문제 분석

좌표 압축의 문제를 읽어보면, 2가지에 초점을 맞추면 쉽게 문제를 해결할 수 있다.

1. N개의 좌표에서 좌표 X를 압축한 결과 X'는, X보다 작은 서로 다른 좌표의 개수이다.
   
   여기서 좌표는 중복될 수 있기에, '서로 다른'에 집중해야한다. 
   ex) 만약 좌표 X = 3이라 할 때, X보다 작은 좌표가 { 1, 1, 2 } 가 있다고 가정하자. 이 경우, 압축 좌표 X' = 2이다.
   
   
2. 입출력값이 정렬되지 않는다.
   
   입력받은 좌표를 정렬시킨다면, 자신(좌표 X) 이하의 좌표 개수가 곧 압축된 좌표의 값이다.
   하지만 정렬시킬 경우, 출력값을 다시 원래 위치로 되돌려놓은 채로 출력해야한다.

---

문제 풀이

결국 정렬이 가장 중요하다.

위 1번.입력받은 숫자를 중복된 번호를 제외한 채 '정렬'한다면 좌표 압축은 쉽게 할 수 있다.

 

(unique함수를 통해 중복된 숫자를 정렬 뒤에 두고, erase함수로 삭제하는 풀이도 있지만...

필자처럼 직접 제거할 수도 있다!)

 

ex) { 2 4 -10 4 -9 } -> { -10, -9, 2 4 }

이를 통해서 좌표 X는 자신보다 앞에 있는 원소의 수가 곧 압축 좌표 X'가 된다.

---

위 2번. 여기서 핵심은 '압축 좌표를 어떻게 출력할 것인가?'이다. 이 때, 우리는 c++에 있는 lower_bound라는 함수를 활용할 예정이다.

💡lower_bound란?

lower_bound(iterator first, iterator last, value) -> iterator 반환
: 이분탐색을 활용하여 찾고자 하는 값보다 크거나 같은 값 중 가장 처음 나오는 값을 반환하는 함수입니다.
  (찾고자 하는 값이 없다면 end값을 반환)
: algorithm 헤더에 내포되어있는 함수.
: 시간복잡도 : O(logN) -> 이분탐색이기에

 

+ iterator값을 반환하기에 iterator값에 시작 iterator를 빼주어 index를 출력하도록 한다.

 

EX)

{ -10, -9, 2, 4 }로 정렬된 배열과, { 2, 4, -10, 4, -9 }로 입력받은 배열을 따로 저장해둔다.

1. 2의 압축좌표는? -> index 2에 위치하기에, 자신보다 작은 좌표가 2개이다. 출력 : 2

2. 4의 압축좌표는? -> index 3에 위치하기에, 자신보다 작은 좌표가 3개이다. 출력 : 3

3. -10의 압축좌표는? -> index 0에 위치하기에, 자신보다 작은 좌표가 0개이다. 출력 : 0

4. 4의 압축좌표는? -> index 3에 위치하기에, 자신보다 작은 좌표가 3개이다. 출력 : 3 

5. -9의 압축좌표는? -> index 1에 위치하기에, 자신보다 작은 좌표가 1개이다. 출력 : 1

 

C++ 풀이

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N;
	cin >> N;
	vector<int> vec(N, 0);

	for (int i = 0; i < N; i++)
		cin >> vec[i];

	vector<int> copy = vec; // copy : vec을 정렬시킨 배열
	vector<int> already; // already : unique한 숫자 정렬된 채로 나열.

	sort(copy.begin(), copy.end()); // 시간복잡도 : O(NlogN)

	for (int i = 0; i < N; i++) {
		if (already.empty()) {
			already.push_back(copy[i]);
			continue;
		} 

		else {
			if (already.back() == copy[i]) {
				already.pop_back();
			}
			already.push_back(copy[i]);
		}
	}
    // 중복 제거 과정.
    
	for (int i = 0; i < N; i++) {
		int it = lower_bound(already.begin(), already.end(), vec[i]) - already.begin();
        // 매우 중요함.

		cout << it << ' ';
	}

	return 0;
}

코드 리뷰는 언제나 환영입니다!