Taxol

I’ve always been.

백준 18870 - 좌표 압축

Updated:

C++

18870 번 - 좌표 압축

문제

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

문제 출처

접근 방법

좌표 압축이란 말이라 이해하기 조금 어려웠지만, 결국 주어진 값들을 작은 순서부터 정렬한 후 그 순번을 처음 주어진 값에 맞추어 출력하는 문제이다.
첫번째 방법으로 주어진 배열을 정렬한 후, 중복을 제거한다.
첫번째 입력과 같이 [2 4 -10 4 -9]와 같다면 정렬 및 중복 제거 후 [-10 -9 2 4]가 되며, 이 순서가 좌표를 압축한 것이 된다.
이후 처음 입력 받은 값에 따라 정렬 된 위치의 순서를 대입해주어야 하는데, 정렬 된 수의 위치를 찾는 것이 단순 탐색으로는 시간초과가 나 이진 탐색을 이용하여 탐색하였다.
이진 탐색은 정렬 된 배열에서 필요한 값을 찾는데 시간을 단축 시켜주며, 이는 O(log2N)의 시간복잡도를 가진다.

구현

algorithm 헤더의 sort와 unique 메소드를 이용하여 정렬과 중복을 제거한다.
처음에는 직접 이진탐색을 구현하였지만, 시간초과가 나 할수 없이 STL의 lower_bound 메소드를 이용하여 해결하였다.

코드

/*
18870번 - 좌표 압축
https://www.acmicpc.net/problem/18870
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<int> arr;
vector<int> backup;

// lower_bound를 직접 구현한 이진 탐색 함수.
int BinarySearch(vector<int> arr, int key) {		
	int len = arr.size();
	int start = 0;
	int end = len - 1;
	int mid;

	while (end - start >= 0) {
		mid = (start + end) / 2;	// 중간을 기점으로,
		if (arr[mid] == key)		// 해당하는 값을 찾으면 그 위치를 리턴
			return mid;
		else if (arr[mid] > key) {	// key가 중간보다 왼쪽에 있으면,
			end = mid - 1;			// 끝을 중간보다 1만큼 왼쪽으로 두어 절반을 탐색한다.
		}
		else {						// key가 중간보다 오른쪽에 있을 시
			start = mid + 1;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	int iptN;
	for (int i = 0; i < n; i++) {
		cin >> iptN;
		arr.push_back(iptN);		// sort 및 중복을 제거하는 배열
		backup.push_back(iptN);		// 기존 배열
	}
	// 정렬 후 중복을 제거하는 작업
	sort(arr.begin(), arr.end());	
	vector<int>::iterator iter;
	iter = unique(arr.begin(), arr.end());
	arr.erase(iter, arr.end());

	// 처음 주어진 입력의 값의 순서를 찾는다.
	for (int i = 0; i < backup.size(); i++) {
		//cout << BinarySearch(arr, backup.at(i)) << " ";		<- 아래의 lower_bound 메소드와 같이 이진 탐색이지만, 시간 초과가 나온다.
		cout << lower_bound(arr.begin(), arr.end(), backup.at(i)) - arr.begin()<< " ";		// c++ STL에서 제공하는 함수 사용.
	}
	
	return 0;
}

추가 접근 및 구현

위의 방법으로 너무 c++의 STL을 사용한 것 같아 새롭게 접근 하였다.

  1. 입력 값을 받을 때, 처음 인덱스를 같이 저장하며 위와 동일하게 처음은 정렬을 한다.
  2. 정렬 된 작은 값 부터 탐색을 하며 이 값의 second 값 즉, 처음 위치를 ans[n]의 index로 두어 출력의 위치를 정한다.
  3. 중복되는 값은 순서가 같으므로, 정렬 된 값에서 이전 값과 현재 값이 같으면 순서를 늘리지 않고, 다르면 cnt를 증가시켜 순서를 증가시킨다.

코드

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

using namespace std;

int n;
vector<pair<int,int>> arr;
int* ans;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	int iptN;
	for (int i = 0; i < n; i++) {
		cin >> iptN;
		arr.push_back(make_pair(iptN,i));
	}
	ans = new int[n];
	sort(arr.begin(), arr.end());
	
	int cnt = 0, val = arr[0].first;	//cnt는 압축된 좌표, val은 이전 값
	ans[arr[0].second] = 0;				//정렬 된 배열의 제일 앞의 second(처음 위치)를 ans의 index로 둔며, 이 값은 0이다.
	for (int i = 1; i < arr.size(); i++) {
		if (val == arr.at(i).first)		// 중복 된 값일 시 순서는 유지
			ans[arr[i].second] = cnt;
		else {
			ans[arr[i].second] = ++cnt;	//다르면 순서가 증가.
			val = arr[i].first;
		}
	}
	for (int i = 0; i < n; i++)
		cout << ans[i] << " ";
	return 0;
}

총평

난이도

⭐⭐⭐★★

후기

간단한 것 같으면서도 되게 해결하지 못하여 끙끙대었다.
요즘 해이해진 것 같아 갑자기 두렵다.

개선할 점

이진 탐색을 생각하고 구현하였지만 왜 시간 초과가 나는지 모르겠다.

You may also enjoy