백준 18870번(silver 2) : 좌표 압축 - 딕셔너리 컴프리헨션

 

18870번: 좌표 압축

---

 

 내가 작성한 정답 - 시간초과 

import sys

n = int(input())
co = list(map(int, sys.stdin.readline().split()))

sortedco = sorted(co)
li=[[sortedco[0], 0]]
compressed_num = 0

for i in range(1, n):
    if sortedco[i] != sortedco[i-1]:
        compressed_num = i
    new_li = [sortedco[i], compressed_num]
    li.append(new_li)

tup_li = list(set(map(tuple, li)))
li = list(tup_li)

new_co = []
for i in range(n):
    com = []
    for j in range(len(li)):
        if co[i] == li[j][0]:
            new_co.append([co[i], li[j][1]])

for i in new_co:
    print(i[1], end=' ')

 

거의 한 시간 정도 걸려서 겨우 풀었는데 계속 시간 초과가 났다.

vs코드로 돌려봐도 결과값은 잘 나오고, 입력할 때 sys.stdin.readline 도 사용했는데 무엇이 문제인지 몰라서 결국 찾아보았다.

 

 

 수정한 정답 

import sys

input = sys.stdin.readline

n = int(input())
co = list(map(int, input().split()))

tem_co = sorted(list(set(co)))
co_num = {tem_co[i] : i for i in range(len(tem_co))}

for i in co:
    print(co_num[i], end=" ")

 

우선, 시간초과와는 별개로 너무 간단하게 구현할 수 있어서 살짝 허무했다.

내가 처음에 작성한 코드의 절반 가량 줄여서 작성할 수 있다니...

그리고 sys.stdin.readline 도 input 에 대입해서 구현할 수 있는 것도 새롭게 알았다.

 

시간초과가 일어난 것은 딕셔너리로 수정하면 해결될 문제였다.

만약 100,000개가 입력됐을 때, 리스트로 접근하면 시간복잡도는 O(n)이기에 100,000번 봐야한다.

하지만 딕셔너리 key, value 값을 이용해 접근한다면 시간복잡도는 O(1)이다.

 

그리고 중복값이 몇개냐에 따라 그 뒤에 나오는 압축 좌표에 영향을 주는 줄 알았다.

예를 들어 10, 10, 10, 20, 20, 30 가 있다면, 10은 1, 20은 4, 30은 5가 될 줄 알았는데, 그냥 10은 1, 20는 2, 30은 3이었다. ㅠ

문제를 잘 읽을 걸. 주어진 예제 입출력 보면 알 수 있었을텐데

 

그리고 리스트 컴프리헨션처럼 딕셔너리 또한 가능하다는 점도 이 문제를 풀면서 처음 알게 되었다.