[#18870] 좌표 압축

문제

#18870 좌표 압축
Silver2
적용 알고리즘: 정렬 알고리즘

---

풀이 방법

• 입력 숫자를 집합(set)으로 전환한 뒤 리스트로 다시 전환하면서 리스트 내의 중복을 제거한다.
• 리스트를 정렬하기 위해서는 sort 내장함수를 사용한다.
• 값 탐색을 위해서 리스트보다 상대적으로 시간이 빠른 딕셔너리 자료구조를 사용한다. (리스트를 통해 탐색 시 시간초과 발생)

코드 흐름

1. 사용자에게서 값을 입력받는다.
2. 입력 리스트에서 중복된 값을 없애기 위해 이를 set으로 변환하고, 다시 오름차순으로 정렬하기 위해 list로 변환하고 이를 내장함수 sort를 사용해 오름차순으로 정렬한다.
3. 딕셔너리를 생성하고, 정렬된 리스트의 가장 낮은 숫자부터 딕셔너리에 키 값으로 저장하고 value의 값을 0부터 할당해준다.
4. 처음 입력받은 리스트의 값을 차례대로 딕셔너리에서 찾아서 출력한다.

코드

n = int(input())
num = [int(m) for m in input().split()]

new = list(set(num))
new.sort()

dic = {}
for i in range(len(new)):
    dic[new[i]] = i

for i in num:
    print(dic[i], end=" ")

아래와 같이 리스트의 인덱스를 이용하여 접근하려하면 시간초과 발생!

for i in num:
    print(new.index(i), end=" ")

체감 난이도: 4.1/5
처음에는 리스트를 사용하여 탐색하려 했지만 시간초과가 발생하여 찾아보니 리스트보다 딕셔너리가 빠르다고 하여 사용하였다. 리스트에서 탐색은 시간복잡도 O(n)가 소요되고, 딕셔너리는 O(1)의 시간복잡도가 걸린다고 한다.

---

[문제풀이 팁]

시간초과가 발생하는 문제는 상대적으로 빠른 딕셔너리 사용
딕셔너리는 hash table를 사용하여 자료를 저장하므로 탐색에 걸리는 시간은 O(1)이다. 인덱스로 접근하는 리스트와 비해서 빠른 탐색 시간을 가진다. 추가로, 딕셔너리에 키와 value를 저장하기 위해서는

dic[3] = "hello"
dic = {'a': [1, 2]}

와 같은 식으로 저장할 수 있다.