백준(baekjoon) 18870번: 좌표 압축(실버 2, 파이썬 PYTHON) - 정렬

문제

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

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

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

 

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

 

import sys

N=int(sys.stdin.readline())
num_list=list(map(int,sys.stdin.readline().split()))
dict={}
result=[]

duplicate_list=list(set(num_list))
duplicate_list.sort()

for x in range(len(duplicate_list)):
  dict[duplicate_list[x]]=x  

for x in num_list:
  result.append(dict[x])  

print(*result)

 

※ 정렬

 

 

● 먼저 입력받은 숫자들을 num_list 배열에 저장해준다.

 

● 그 후 num_list의 요소들이 중복되지 않도록 set 함수를 이용하여 중복요소를 제거한 배열을 duplicate_list 배열에 저장해준 뒤, 이를 오름차순으로 정렬한다. 그러면 duplicate_list의 요소들이 갖는 인덱스 값이 그 요소 값보다 작은 요소들의 개수를 의미하게 된다.

 

● 시간 초과 발생을 방지하기 위해 duplicate_list 요소들의 각 값을 key로 하고, 그 key의 value가 duplicate_list 안에서 그 key값의 인덱스인 딕셔너리 dict를 선언해준다.

 

● 마지막으로 num_list를 돌며 각 요소 값을 key로 하는 value 값을 result 배열에 순서대로 append 해준 뒤 출력해주면 끝!!

 

 

결과

 

 

♣ 참고: 파이썬 set

https://wikidocs.net/16044

18. set(집합)