[백준 BOJ/C++] 18870 좌표 압축

18870번: 좌표 압축

 

정렬을 통해 풀어내는 문제고 실버 II 난이도라서 쉽게 생각했지만 의외로 까다로운 문제다.
조건이 타이트하진 않지만 문제 설명이 자세하지 않고 생각을 좀 해야 풀이 방법에 다가갈 수 있다.
특히 사용하는 언어에 따라 난이도 차이가 심해질 수 있는 문제다.

 

 

우선 문제 설명이 짧은 편이라 단번에 파악하기 어려울 수 있는데 간단히 표현해 입력 받은 각 좌표들 보다 작은 좌표의 갯수를 출력하면 된다.

여기에서 한가지 조건을 추가해 압축이라는 형태를 만들었는데 바로 중복된 좌표는 1개로 간주해야 한다는 것이다.

 

 

이정도만 파악하면 문제가 간단해 보이지만 의외로 풀어가다보면 고민해야 하는 지점이 몇가지 있었다.

다른 언어에서는 훨씬 간단할 수 있지만 적어도 C나 C++에서는 쉽게 풀어내기에 불편한 부분들이 있다.

 

 

---

 

 

문제의 포인트

 

중복 좌표의 제거 방법
더 작은 좌표의 갯수를 찾을 방법

 

 

중복 좌표의 제거 방법 

 

 

일직선 상의 데이터들 간 대소 비교가 필요한 문제이기 때문에 정렬이 필요하다.

각 좌표보다 작은 좌표의 갯수를 찾는 문제이므로 정렬 이후 정렬된 데이터의 index를 활용하면 간단해 보인다.

 

 

추가적인 조건으로 입력으로 주어진 좌표들의 순서에 맞춰 출력해주어야 하기 때문에 입력 받은 배열은 그대로 유지시키고 정렬시킬 배열을 따로 만드는 것이 좋을것 같다.

입력 받을 때 2벌을 만드는 형태로 간단히 해결 가능하다.

 

 

문제는 정렬한 데이터의 index를 출력하면 중복된 데이터가 포함된 갯수라는 것이다.

중복된 좌표를 제외하고 카운트 하기 위해서는 정렬 이후 중복 제거 과정까지 거친 데이터에서 위치를 찾아야 한다.

 

 

1. 입력 받은 데이터를 2벌로 준비
2. 2중 한개의 배열을 정렬시킴
3. 정렬된 배열에서 중복 제거
4. 배열에서 각 데이터의 위치를 기반으로 더 작은 좌표 갯수 출력

 

 

 

 

배열에서 중복을 제거하는 방법은 어떤것이 있을까?

사실 문제를 풀고나서 알게된 것인데 vector library와 unique 를 활용하면 간단히 해결할 수 있다.

unique 함수를 이용하면 배열에서 연속으로 중복되어있는 데이터를 맨 뒤로 보내준다.

아래 처럼 vector의 erase 멤버함수를 함께 이용하면 이러한 중복 데이터를 배열에서 삭제할 수 있다.

 

 

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

 

 

하지만 문제 풀이 당시 C++ 보다는 C가 훨씬 익숙했고 알고리즘 문제 풀이에 불편을 느껴 C++ 로 옮겨온지 얼마 안되었기 때문에 이러한 방법을 몰랐었다.

조금 귀찮지만 C 에서 활용하던 방식으로 중복을 제거했다.

 

 

바로 또 하나의 빈 배열을 만들고 정렬된 배열을 1번 전체 순회하면서 중복 없이 unique한 데이터만 새 배열로 복사하는 방법이다.

메모리 제한 압박이 크지 않다면, 그리고 C언어와 같이 알고리즘 문제 풀이에 활용하기 좋은 library가 충분치 않은 경우 활용할 수 있는 방법이다.

 

 

더 작은 좌표의 갯수를 찾을 방법

 

 

이제 처음 입력 받은 순서대로 각 값이 정렬 및 중복제거까지 한 배열에 어디에 위치하는지 찾아서 그 index를 출력해주면 풀이가 끝난다.

하지만 원소의 개수가 최대 1,000,000개로 많기 때문에 각 원소 마다 무식한 탐색을 했다간 시간 초과가 발생할 가능성이 커 보인다.

 

이진 탐색과 같은 효율적인 탐색 방법을 활용해야 하는데 algorithm library에서 이것을 쉽게 해결해주는 함수를 제공한다.

lower_bound 를 사용하면 배열의 특정 범위 내에서 특정 값을 O(logN) 의 시간 복잡도로 찾아준다.

이 함수는 찾은 item의 index가 아닌 주소를 그대로 반환하기 때문에 index를 취하기 위해서는 배열의 시작 주소를 빼주면 된다.

 

 

cout << lower_bound(array, array + N, target_num) - array;

 

 

---

 

전체 Code

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int X[1000000 + 10];
int Xp[1000000 + 10];
int compX[1000000 + 10];

int pos;

void compress() {
	int i;

	compX[0] = Xp[0];
	pos = 1;

	for (i = 1; i < N; i++) {
		if (Xp[i - 1] != Xp[i]) {
			compX[pos] = Xp[i];
			pos++;
		}
	}
}

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);

	int i;

	cin >> N;
	for (i = 0; i < N; i++) {
		cin >> X[i];
		Xp[i] = X[i];
	}

	sort(Xp, Xp + N);
	compress();
	
	for (i = 0; i < N; i++) {
		cout << lower_bound(compX, compX + pos, X[i]) - compX << " ";
	}
	cout << "\n";

	return 0;
}