정렬 - 좌표 압축

백준 18870

 

정렬 - 좌표 압축

 

문제.

 

수직선 위에 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을 공백 한 칸으로 구분해서 출력한다.

 

제한.

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

>> 몹시 문제가 불친절하다. 해당 숫자의 순위를 출력하는 문제.

     서로 다른 좌표의 개수 -> 중복제거, 나보다 작은 숫자의 개수

 

접근.

바로 생각 든 것이 카운트정렬이었다.

초기값을 0 으로하고 카운트 정렬 할 시에 자신의 순위를 단박에 알 수 있다.

그리고 10^9 만큼 배열을 선언해서 실행해보니 컴퓨터가 윙~ 거렸으므로.. 패스..

배열은 주어진 입력에 맞춘 크기만큼 사용하기로 결정.

입력받은 대로 해당index의 딕셔너리 데이터타입에 맞춰 1씩 플러스

이제 중복 만 제거해주면 되는데.. 로직을 통해 중복제거하려 했으나 2차시도 까지 실패..

입력 받을 때 중복을 제거하니 성공..!

 

N=int(input())
d={}
arr=list(map(int,input().split()))
arr2=sorted(list(set(arr)))
a=0
for _ in arr2:
	d[_]=a
	a+=1
ans=[]
for _ in arr:
	ans.append(str(d[_]))
print(" ".join(ans))

 

>> 중복 제거를 입력 받고 난 후, 해결 하는 법을 생각해 보자.

     카운트정렬 갓