[백준] 18870번: 좌표압축 - python

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

18870번: 좌표 압축

 

사실 처음 보고 O(n^m) 제곱으로 순간 하면 편하겠다.. 라고 생각했지만 알고리즘을 공부하는 사람으로 그짓은 이제 못하겠다.

 

무조건 해시맵이나 집합 자료형을 쓰는 거라고 생각했고, 코드를 작성했다.

 

처음에 입력받고, 입력받은 것을 토대로 set자료형으로 받고 정렬을 위해 리스트로 반환한다.

 

그 다음 dic로 인덱스와 값을 순서대로 저장한다.

 

마지막으로 arr를 순회하며 dic[값]을 찾아 반환하면 갯수가 나오게 된다.

 

n = int(input())
arr = list(map(int, input().split()))

arr2 = sorted(list(set(arr)))
dic = {arr2[i] : i for i in range(len(arr2))}
for i in arr: 
    print(dic[i], end = ' ')  #키에 저장하고 출력

 

완성