백준 1094번 막대기 파이썬 풀이

처음 문제를 보고 구현하는 방법이 그대로 적혀있길래 쓰인대로 구현해서 통과했었는데,

1. 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.

이 부분을 가장 짧은걸 자르라길래 우선순위 큐를 이용해서 구현했었습니다

import heapq

target = int(input())
heap = [64]
while sum(heap) != target:
    splited = heapq.heappop(heap) // 2
    if splited < 1: continue
    heapq.heappush(heap, splited)
    if not target < sum(heap): heapq.heappush(heap, splited)
print(len(heap))

그래서 이렇게 코드를 짜서 통과했는데 코드를 보니까 어차피 힙에 새로 추가되는건 잘린 막대이기 때문에 무조건 최소값이라 우선순위 큐를 쓸 필요가 없더라고요

target = int(input())
stack = [64]
while sum(stack) != target:
    splited = stack.pop() // 2
    if splited < 1: continue
    stack.append(splited)
    if not target < sum(stack): stack.append(splited)
print(len(stack))

우선순위가 필요 없단걸 알게 된 후에 바로 기본 스택을 이용하는식으로 코드를 고쳤어요

우선순위 큐에서 스택으로 바꾸고 난 결과

코드를 고치고 나니 메모리 사용량도 조금 줄었고 시간이랑 코드 길이도 조금씩 준걸 볼수 있었습니다!