BOJ 18870 좌표압축

18870번: 좌표 압축

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

www.acmicpc.net

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

난이도는 solved.ac 기준 실버 2

좌표 압축 : 들어온 좌표의 크기를 순서대로 정렬하고, 인덱싱을 새롭게 0부터 시작하도록 한다. 알고리즘 기법으로 좌표의 범위가 너무 큰 경우 인덱싱을 통해 좌표 사이 갭을 없애고 크기를 줄임.

단순히 Int값을 ArrayList와 Collections Sort를 통해서 정렬을 진행한다.

그 다음 HashMap을 통하여 key= 좌표값, Value = 인덱스 값을 넣어준다.

마지막으로 Map.get(key) 를 통해 인덱스 값을 출력해준다. (* 단 System.out.print() 를 사용할 경우 시간초과가 발생하므로 StringBuilder나 BufferWrite 등의 더 빠른 출력 메서드를 사용하도록 한다.)