[알고리즘][파이썬] 백준_18870_좌표 압축

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

18870번: 좌표 압축

N개의 숫자를

작은 숫자 부터

0부터 시작하는 순위를 매겨야 한다.

같은 숫자는 같은 순위이다.

---

1차 시도(시간 초과)

# 이중 for문(결과: 시간 초과)
import sys

N = int(sys.stdin.readline())
ipt = list(map(int, sys.stdin.readline().split()))

idx = list(sorted(set(ipt)))

for i in ipt:
    for j in range(len(idx)):
        if i == idx[j]:
            print(j, end = " ")

 

예제 입력 1, 2 모두 정확하게 출력되었다.

그래서 제출했지만

"시간 초과"

 

시간 복잡도를 고려해야 하는 문제였다.

복잡한 정도는 다음과 같다.

O(1) < O(log(n)) < O(nlog(n)) < O(n2)

 

"Complexity of Python Operations"을 참고하여 복잡도 O(1)인 딕셔너리를 이용하기로 하였다.

https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

---

딕셔너리 이용(맞았습니다)

# 딕셔너리 이용(결과: 맞았습니다!)
import sys

N = int(sys.stdin.readline())
ipt = list(map(int, sys.stdin.readline().split()))

idx = list(sorted(set(ipt)))

dic = {}
for i in range(len(idx)):
    dic[idx[i]] = i
    
for i in ipt:
    print(dic[i], end = ' ')

 

이중 for 문 대신

딕셔너리 이용하여 제출,

시간 복잡도 문제가 해결되었다!