[Algorithm][Python] 백준(BOJ) 18870 좌표 압축

[문제]

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

---

풀이

[내 코드]

import sys

n = int(input())
input_arr = list(map(int, sys.stdin.readline().split()))
set_arr = sorted(set(input_arr))
dic = {set_arr[i]: i for i in range(len(set_arr))}

for i in input_arr:
    print(dic[i], end=' ')

좌표 압축이란?

여러 곳에 흩뿌려진 좌표들을 연속된 수들로 모아 압축하는 것을 말한다.

풀이

• Set 함수를 통해 중복을 없앤 후, 정렬을 시킨 새로운 리스트(set_arr)에 저장한다.
• Dict자료형을 사용하여 set_arr를 돌면서 key는 해당 값, value는 인덱스 값을 넣어준다.
• 입력받은 리스트를 돌면서 순회 값과 dict에서 key값이 같은 value 를 출력한다.

💡주의

• Dict 자료형을 사용하지 않고 list.index(i)로 사용하게 되면 시간복잡도 O(N)으로 시간초과가 난다.
• 시간복잡도가 O(1)인 Dict 자료형을 사용하자!!