[C++] BOJ 18870번 : 좌표 압축

시간제한	메모리제한	알고리즘 분류
2 초	512 MB	정렬, 값 / 좌표 압축

 

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

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

출력

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

제한

•  1 ≤ N ≤ 1,000,000
• -10^9 ≤ Xi ≤ 10^9

---

문제 해결 조건

좌표 압축 결과가 xi > xj를 만족하는 다른 좌표 개수를 출력해야한다.

즉, 입력받은 각 숫자 자기 자신보다 작은 수의 갯수를 입력받은 순서대로 다시 출력한다.

 

해결하기 위한 설계 1차

1. 입력받은 좌표 x값을 저장하는 배열 혹은 벡터를 만든다.

2. 이중 for문을 통해 arr[i]에서 Xi > Xj 조건을 만족하는 원소의 갯수를 계산한 뒤, 출력 배열에 순서대로 저장한다 

3. 저장한 배열을 출력한다

 

1차 시도의 문제점

arr[i]와 arr[j]로 이중 for문을 작성해 돌리게 되면, 시간복잡도가 O(n^2)가 되어 시간 제한을 초과하게 된다.

따라서, 반복문의 중첩을 줄이는 설계가 필요하다. 

 

해결하기 위한 설계 2차

1. 입력받은 배열 arr를 오름차순으로 정리한다. 

2. arr 내에서 가장 작은 수는 압축된 좌표 X'1 = 0을 갖고, 가장 큰 수는 압축된 좌표 X'n = n을 갖는다.
* 단, 이때 중복된 좌표를 처리해야함!

3. 중복된 좌표를 처리하기 위해, if(arr[n] == arr[n+1]) pop().. 등 조건을 부여해 좌표를 동일하게 만든다.

4. 처리된 좌표를 원래의 배열 순서대로 다시 출력한다. 

 

2차 시도의 문제점

해결을 위한 전체적인 흐름은 대략적으로 이해가 가지만, 반복의 중첩을 해결하기 위한 개념이 있을 것이라 생각해서 '좌표압축'을 키워드로 구글링을 시도함. 검색 결과 STL 함수들을 발견할 수 있었음.

 

다시 문제 파악을 하는 지점으로 돌아가서, 몇가지 놓쳤던 점을 추가한 설계는 다음과 같다.

1. 입력받은 숫자들을 임시 배열에 저장하고 오름차순 정렬한다. 

2. 중복되는 숫자는 삭제한다. 이를 위해 erase()와 같은 STL 함수를 사용한다. 

3. 자기자신 보다 작은 숫자를 탐색할 땐, 메모리 효율과 시간 절약을 위해 이분탐색(Binary Search)을 사용한다.

 

좌표 압축이란?

좌표 압축(Coordinate compression)은 ps의 카테고리중 하나로 취급된다. 데이터 사이의 갭이나 중복된 데이터를 삭제하여 광범위한 범위의 좌표들을 작은 범위로 매핑한다. 압축을 통해 메모리와 시간을 효율적으로 사용할 수 있다. 1차원 상의 압축도 쓰이나 특히 2차원상의 압축이 강력하다.  

1차원 좌표압축(Coordinate compression in 1D) / 출처 : Algorithms digest (medium)

 

std::vector::erase()와 std::vector::resize(), std::unique(), 그리고 std::lower_bound()

erase()

: Removes from the vector either a single element (position) or a range of elements (first,last).

erase()는 특정 반복자 위치의 엘리먼트를 지우거나 지정한 범위(first에서 last까지)의 엘리먼트를 지운다. 

iterator erase (iterator position);
iterator erase (iterator first, iterator last);

resize()

: Resizes the container so that it contains n elements.

n만큼의 사이즈로 벡터를 리사이징한다. 만약 현재 사이즈보다 n이 큰 경우, 새로 리사이징한 벡터의 element에 val값을 카피한다.

void resize (size_type n);
void resize (size_type n, const value_type& val);

unique()

: Removes all but the first element from every consecutive group of equivalent elements in the range (first,last).

 unique()는 지정한 범위 내의 중복을 중복이 아닌 데이터의 뒤로 보낸 후 제거하고, 포인터가 가장 첫 중복의 인덱스를 가리키게 한다. 선형적으로 이루어지므로 last-first 원소 갯수만큼의 시간을 소모한다.

template <class ForwardIterator>
  ForwardIterator unique (ForwardIterator first, ForwardIterator last);
  ForwardIterator unique (ForwardIterator 범위 시작, ForwardIterator 범위 끝);

template <class ForwardIterator, class BinaryPredicate>
  ForwardIterator unique (ForwardIterator first, ForwardIterator last,
                          BinaryPredicate pred);

lower_bound()

: Returns an iterator pointing to the first element in the range (first,last) which does not compare less than val.

lower_bound는 범위내의 데이터 중에서 val값을 가장 먼저 출력하는 첫 번째 엘리먼트를 가리키는 iterator이다.

lower_bound()의 반환형은 iterator이므로, 그냥 출력할 수는 없으며 실제 타겟 인덱스 값을 알고 싶다면 벡터의 경우 v.begin()을 빼주고 배열의 경우 array 그 자체를 뺀다.

template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                               const T& val);

해결하기 위한 설계 3차

입력받은 배열을 복사할 임시 배열을 만든다. 이 임시 배열은 후에, 원본 배열이 정렬되기 전 데이터를 보관하고 있다. 이에 따라, 임시배열에 iterator인 e가 처음 나오는 인덱스를 반환하는 lower_bound()를 써서 오름차순 Xi> Xj를 만족하는 압축된 좌표를 반환한다.

제출 코드

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

using namespace std;

void solve() {

	int n;
	cin >> n;
	vector<int> pt;
	vector<int> cpy;

	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		pt.push_back(x);
		cpy.push_back(x);
	}

	sort(pt.begin(), pt.end());
	pt.erase(unique(pt.begin(), pt.end()), pt.end()); //resize()를 써도 됨.

	for (auto& e : cpy) {
		int cmp = lower_bound(pt.begin(), pt.end(), e) - pt.begin(); //iterator인 e가 처음으로 나온 index 위치를 저장
		cout << cmp << " ";
	}
}

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

아직 vector 이외의 컨테이너를 모르기 때문에 lower_bound()도 쓰고 index를 복잡하게 사용한 것 같다..

더 공부해야지. 더 효율적인 코드가 없을까?라는 생각에, 제출된 코드들을 살펴보던 중에 새로운 문법을 찾았다..

이런 방식의 벡터 선언도 가능하구나..