[Python] 18870 좌표 압축

👉 18870 좌표 압축

[정답 코드]

import sys
import heapq

input = sys.stdin.readline

n = int(input())
x_list = list(map(int, input.split()))
x_heap = []
result = [0] * n
dic_for_same_num = {}
for i in range(n):
    heapq.heappush(x_heap, (x_list[i], i))

for i in range(n):
    t = heapq.heappop(x_heap)
    value = t[0]
    index = t[1]
    if dic_for_same_num.get(value) == None:
        dic_for_same_num[value] = len(dic_for_same_num)
    result[index] = dic_for_same_num.get(value)

for i in result:
    print(i, end='')

[풀이]

1. python heapq을 이용해 제일 작은 값을 하나씩 heappop 하면서 dict에 넣었다.
2. 조건에 따르면, 값이 같은 좌표는 카운팅될 수 없으므로 dict.get()을 통해 좌표(key)가 이미 dict에 있는 확인한 후 없다면, len(dict)의 값을 value로 넣어준다. (이미 dict에 있는 좌표들(key)은 모두 방금 heappop된 좌표보다 작은 값들이기 때문)

집합(set)을 이용하면 위와 같이 더 쉽게 풀 수 있다.

import sys
input=sys.stdin.readline
print=sys.stdout.write

N=int(input())
arr=list(map(int,input().split()))
sort_arr=sorted(set(arr))
arr_dict={i:v for v,i in enumerate(sort_arr)}
for i in arr:
    print(f'{arr_dict[i]} ')

enumerate

반복문 사용 시 몇 번째 반복문인지 확인이 필요할 때 쓰임
인덱스 번호와 컬렉션의 원소를 tuple형태로 반환

[적용 자료구조 및 알고리즘]

• Heap
• Dictionary
• Set