인프런 커뮤니티 질문&답변

녹조현상님의 프로필 이미지

작성한 질문수

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

10. 최소힙

최소힙 문제를 이분정렬로 풀어보았습니다. 코드 조언 부탁드릴게요!

23.01.26 14:38 작성

·

289

0

from collections import deque 
List = []
List = deque(List)

List2 = []

while(True):
    x = int(input())
    if x != 0 and x != -1:
        m = 0
        n = len(List) -1
        answer = len(List)
        if List:
            while(m <=n):
                if x <= List[(m+n)//2]:
                    answer = (m+n)//2
                    n = (m+n)//2 -1
                else:
                    m = (m+n)//2 + 1
            

            List.insert(answer, x) 
        else:
            List.append(x)
    elif x == 0:
        if len(List) == 0:
            List.append(-1)
        else:
            List2.append(List.popleft())
    else:
        break



for _ in List2:
    print(_)

정답 출력을 위해 List2 로 정답들을 담았고

pop 시간을 줄이기 위해 deque를 썼습니다.

이렇게 풀어도 괜찮을까요?

답변 1

0

김태원님의 프로필 이미지
김태원
지식공유자

2023. 01. 29. 09:58

안녕하세요^^

네. 잘하셨습니다. 이 번 영상은 파이썬의 우선순위큐 자료구조를 활용하는 법을 알려드리기 위해서입니다. 영상에서 사용하는 heapq 사용법도 숙지하시기 바랍니다.