백준 18870 문제 풀이

🐒 좌표 압축

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

✍ 나의 풀이

N = int(input())

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

set1 = sorted(set(arr))

dic1 = dict()
for i in range(len(set1)):
    dic1[set1[i]] = i

result = []
for i in arr:
    result.append(dic1[i])

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

---

🧠 문제 이해

지문을 이해 못했는데, 검색을 통해
가장 작은 수의 좌표를 0으로 하여 주어진 수들의 상대 좌표를 나타내는 문제 쯤으로 이해를 했다.

N = int(input())

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

set1 = sorted(set(arr))

result = []
for i in arr:
    print(set1.index(i), end= ' ')

처음엔 이렇게 풀면 되지 않나 싶었는데
index()메소드가 O(N)이므로 시간 초과를 발생시킨다.

따라서 index()대신 딕셔너리에 위치를 저장하는 방법을 이용하면 O(1)만에 위치를 알아낼 수 있다.

---