[회고] 신입 iOS 개발자가 되기까지 feat. 카카오 자세히보기

💻 CS/알고리즘 연습

[알고리즘 연습] 더 맵게 (프로그래머스 lv2, 파이썬)

inu 2021. 6. 9. 21:27
반응형

문제

https://programmers.co.kr/learn/courses/30/lessons/42626

 

코딩테스트 연습 - 더 맵게

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같

programmers.co.kr

풀이

import heapq

def solution(scoville, k):
    heapq.heapify(scoville)
    i = 0
    while scoville[0] < k:
        if len(scoville) > 1:
            heapq.heappush(scoville, heapq.heappop(
                scoville) + (heapq.heappop(scoville) * 2))
            i += 1
        else:
            return -1
    return i
  • 단순 queue 혹은 stack으로는 새로 생성되는 값(섞은 음식의 스코빌 지수)를 정렬하기 어렵다
  • heapq 활용 : 우선순위대로 자동정렬해주는 자료구조 (우선순위 큐)
  • heapq.heapify(list) : 자료구조 heap화
  • heapq.heappush(heap, item) : 힙 구조를 유지하면서 값 삽입
  • heapq.heappop(heap) : 가장 작은값 반환
  • scoville[0]은 scoville에서 가장 작은 값이다. 해당 값이 k보다 작은 이상 계속해서 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)를 반복한다.
  • 만약 scoville의 크기가 1인데 그것이 k보다 작은 스코빌 지수를 가진다면 불가능한 것이므로 -1를 반환한다.
반응형