글 읽기 - 카드정렬 질문입니다.

bloom6561 2년 전 0

위에 우선순위큐로 되어있는게 정답 통과한 코드이고, 제가 원래 생각했던건 arr를 배열로 둬서, 문제를 해결하려고했습니다. 결과는 시간초과가 떴구요.

코드를 비교해봐도 로직 자체는 동일한거 같은데, 우선순위 큐의 자동정렬 알고리즘과 list의 정렬알고리즘의 시간복잡도 차이때문에 시간초과가 뜬걸까요? 이럴때는 출제의도 자체가 heapq나 PriorityQueue처럼 시간복잡도가 낮은 자료구조를 사용해야만 풀리게끔 만드신걸까요?

답변해주시면 정말 감사할 것 같습니다!

import sys
from queue import PriorityQueue

input=sys.stdin.readline

"""
문제를 풀려는 생각 자체는 맞았음.
다만 while문에서 매번 arr.sort()를 호출하는게
시간초과를 이끌어낸듯.
heapq나 PriorityQueue를 이용하면 해결됨.
"""

n=int(input())

s=0
arr=PriorityQueue()

for _ in range(n):
    arr.put(int(input()))

while True:
    if arr.qsize()==1:
        break
    a=arr.get()
    b=arr.get()
    s+=a+b
    arr.put(a+b)
print(s)
"""
while True:
    if len(arr)==1:
        break
    arr.sort()
    temp=arr[0]+arr[1]
    a=arr[0]
    b=arr[1]
    s+=temp
    arr.remove(a)
    arr.remove(b)
    arr.append(temp)
"""

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

카드정렬 질문입니다.

bloom6561 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말