좌표 압축 풀이

문제 링크: https://www.acmicpc.net/problem/18870

백준 정렬 12단계 - 18870번 좌표 압축을 풀어보았다.

 

풀이: 압축한 결과는 좌표의 순서와 같다는 점을 알아내면 된다.

C++의 경우, erase와 unique를 써서 중복을 제거했다. (전에는 입력마다 중복인지 확인했는데, 그러면 시간초과가 난다)

파이썬의 경우, 딕셔너리를 사용해 시간을 줄였다.

 

C++

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

using namespace std;
int main()
{
	ios_base::sync_with_stdio(false); // 시간 빠르게 하기 위해서
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n;
	cin>>n;
	vector<long long> v1; // 모든 입력
	vector<long long> v2; // 중복 아닌 것만
	for(int i=0;i<n;i++)
	{
		long long inp;
		cin>>inp;
		v1.push_back(inp);
		v2.push_back(inp);
        // if(find(v2.begin(),v2.end(),inp)==v2.end()) v2.push_back(inp);
        // 윗줄로 중복판정을 했는데 시간초과 떴다
	}
	sort(v2.begin(),v2.end());
	v2.erase(unique(v2.begin(),v2.end()),v2.end()); // 중복 지우기
	for(int i=0;i<n;i++) cout<<lower_bound(v2.begin(),v2.end(),v1[i])-v2.begin()<<" ";
}

Python

n=int(input())
cor=list(map(int,input().split()))
ncor=list(sorted(set(cor))) # set으로 중복 요소 제거
dic={ncor[i]:i for i in range(len(ncor))} # 정렬해서 순서 매기기
for i in cor:
	print(dic[i],end=" ") # 압축결과=순서

Java