[BaekJoon] 백준 18870번 좌표 압축

[BaekJoon] 백준 18870번 좌표 압축

 

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

 

내코드

 

처음 문제를 풀었을 때 시간초과가 났다. 이유가 뭘지 고민하다가 검색해보니까 다른 사람도 나와 같이 풀어서 시간 초과가 난 경우가 많았다.(역시 사람 생각하는건 다 똑같..) 문제는 index 메서드였다. index 메서드는 O(N)의 시간 복잡도를 가지기 때문에 for문 안에서 N*N이 되어 시간이 오래 걸리는 거였다.

# 틀린 코드

# BaekJoon18870.py

N = int(input())
arr = list(map(int, input().split()))
sorted_arr = sorted(list(set(arr)))
for i in range(N):
    arr[i] = str(sorted_arr.index(arr[i]))

print(" ".join(arr))

해결 방법은 dic를 이용하는 것이었다.

# BaekJoon18870.py

N = int(input())
arr = list(map(int, input().split()))
sorted_arr = sorted(list(set(arr)))
dic = {sorted_arr[i] : i for i in range(len(sorted_arr))}
for i in arr:
    print(dic[i], end = " ")

 

 

 

참고

https://gudwns1243.tistory.com/52