백준 18870. 좌표 압축

tose33 2022. 12. 27. 13:40

18870번: 좌표 압축

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

www.acmicpc.net

vector, pair, sort 를 이용하면 쉬운 문제였다.

1. pair<좌표, 순서> 로 저장하고 <argorithm>의 sort로 정렬하면 좌표 기준 오름차순 정렬된다.

2. pair<순서, 압축값>로 저장. 작은 좌표 부터 압축값을 0 부터 넣어준다. 이전 좌표와 같으면 증가시키지 않고 넣는다.

3. 정렬하면 순서 기준 오름차순 정렬되므로 원래 순서가 복원되고 압축값을 순서대로 출력.