[Python/프로그래머스] 42626. 더 맵게

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

힙

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

---

풀이

from heapq import heappush, heappop, heapify
def solution(scoville, K):
    
    # 가장 낮은 놈 하나 빼서, 그거 지수 + 하나 더 뺌 * 2 한거 push하면 됨
    # 그 push한 결과가 K보다 크면, 거기까지 pop한 횟수(또는 push한 횟수)를 return하면 됨
    
    # 원래 있던 리스트 scoville을 heap으로 바꾸는 게 핵심임.
    # 그냥 저 scoville를 가지고 heappop을 하면, 그냥 예를 들어 [5, 3, 9, 10, 12]라고 하면
    # 그냥 앞에 있는 놈 5가 빠지게 되므로, 의미가 없음.
    
    # 그냥 새로운 heap 배열에다가 다 넣는 방법이 있겠고,
    # heapify라는 함수를 쓰는 방법이 있음. 시간복잡도 O(N)
    # heapify 함수는 매개변수르 들어오는 리스트를 heap 구조로 정렬시킴.
    
    counts = 0
    # 문제 조건에서, scoville가 이미 '힙 구조'로 정렬되어 있다는 말은 없음!!
    # 그러니, scoville를 힙 구조를 가지도록 정렬해줘야함.
    # (힙 정렬을 수행하는 게 아님. 헷갈리지 마!)
    heapify(scoville)
    while scoville[0] < K:
        # 섞는 행위 한 번 하고 나면, len(scoville)는 1씩 줄어든다는 걸 인지!
        # 따라서, len == 1 즉 더 이상 섞을 수 없는데도 scoville[0] < K이라면?
        # => 그 때가 '모든 음식의 지수를 K 이상으로 만들 수 없는 경우'임.
        if len(scoville) == 1:
            return -1
        # 아래처럼 하면 파이썬에선 인자에 들어간 수식들이 왼쪽부터 평가됨.
        heappush(scoville, heappop(scoville) + 2 * heappop(scoville))
        counts += 1
    return counts

    # 참고로, while문 내부의 시간복잡도는 O(3*log(len(scoville)))임. 최악의 경우 1,000
    # 이러한 연산을, 최악의 경우인 scoville의 원소가 모두 0인 경우를 생각해보면,
    # 대략 1회 시행 시마다 len이 1씩 줄으므로, while문 내부가 최악의 경우 1,000번 시행 가능.
    # 따라서, 대략 nlog(n)인데 외부에 heapify는 n이니까 상쇄되고,
    # 1000*3 하면 단위연산 3000이니까 시간복잡도 충분함.
    
    # 여기서, 최악의 경우에 대한 시간복잡도를 분석하는 데 K값은 들어가지 않음. 
    # 왜냐하면, K값이 몇이든간에(사실 0은 제외하고) 최악의 경우 n번 섞어야 한다는 건 변함이 없거든.

주석 제거 버전

from heapq import heappush, heappop, heapify
def solution(scoville, K):
    counts = 0
    heapify(scoville)
    while scoville[0] < K:
        if len(scoville) == 1:
            return -1
        # 아래처럼 하면 파이썬에선 인자에 들어간 수식들이 왼쪽부터 평가됨.
        heappush(scoville, heappop(scoville) + 2 * heappop(scoville))
        counts += 1
    return counts

---

250226 재풀이

조금 다르게 푼 풀이

기존 풀이와 비교하면, while문 종료 조건과 return 조건을 바꿔 썼음.

from heapq import heappop, heappush, heapify
def solution(scoville, K):
    heapify(scoville)
    counts = 0
    if scoville[0] >= K:
        return 0
    # for _ in range(len(scoville)-1):
    while len(scoville) > 1:
        heappush(scoville, heappop(scoville) + 2 * heappop(scoville))
        counts += 1
        if scoville[0] >= K:
            return counts
    return -1

# 모든 음식 지수를 K 이상으로 만들고 싶음.
# 지수 가장 낮은 두 개를 아래로 섞어 새로운 음식을 만듦
# 섞은 음식의 스코빌 지수 = 
# 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
# 즉, 가장 값이 작은 놈과, 그 다음으로 작은 놈을 pop해서, 그 둘의 값으로 하나를 만들어 push.
# 지수 배열 scoville, 원하는 지수 K
# 모든 지수 K 이상 최소 섞어야 하는 횟수 return
# 모든 음식 k 이상 못 만들면 -1 리턴

기존 풀이대로 푼 풀이

from heapq import heappop, heappush, heapify
def solution(scoville, K):
    heapify(scoville)
    counts = 0
    while scoville[0] < K:
        if len(scoville) == 1:
            return -1 # 주어진 횟수(n-1회) 내에서, 모든 걸 K 이상으로 만들 수가 없음.
        heappush(scoville, heappop(scoville) + 2 * heappop(scoville))
        counts += 1
            
    return counts

# 모든 음식 지수를 K 이상으로 만들고 싶음.
# 지수 가장 낮은 두 개를 아래로 섞어 새로운 음식을 만듦
# 섞은 음식의 스코빌 지수 = 
# 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
# 즉, 가장 값이 작은 놈과, 그 다음으로 작은 놈을 pop해서, 그 둘의 값으로 하나를 만들어 push.
# 지수 배열 scoville, 원하는 지수 K
# 모든 지수 K 이상 최소 섞어야 하는 횟수 return
# 모든 음식 k 이상 못 만들면 -1 리턴