[Python] 구름 : [현대모비스] Dead or Arrive

https://level.goorm.io/exam/152114/%ED%98%84%EB%8C%80%EB%AA%A8%EB%B9%84%EC%8A%A4-%EC%98%88%EC%84%A0-dead-or-arrive/quiz/1

구름LEVEL

---

💡 문제 풀이

우선순위 큐를 이용해서 해결했다.

 

딕셔너리 자료형이 key 값을 찾을 때 O(1)의 시간 복잡도를 가져서서 딕셔너리를 사용했다.

또한 최대한 시간복잡도를 줄이기 위해서 heapq를 사용했고 최대 힙으로 구현해서 찾아줬다.

✔️ 느낀 점

sys 안 써서 계속 시간 초과 떠서 너무 열이 받았다..

💻 코드

import heapq, sys
input = sys.stdin.readline

n = int(input())
dict = {}

for i in range(n):
    v, w = map(int, input().split())
    if v not in dict:
        dict[v] = [[-w, -(i+1)]]
    else:
        heapq.heappush(dict[v], [-w, -(i+1)])

tmp, ans = [], 0

for k in dict.keys():
    if k in tmp: continue
    ans += -(heapq.heappop(dict[k])[1])
    
print(ans)