[프로그래머스] 힙-더 맵게 (level.2)

 

문제링크

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

코딩테스트 연습 - 더 맵게

 

나의풀이

초반에는 리스트를 활용해서 최소값을 출력하고, 더해주고 넣어주고 과정을 반복하려고 했다. 하지만, 리스트를 사용할 경우 분명히 시간초과, 효율성테스트를 통과하지 못할 것이라 생각했다. 그래서 일단 바로 heapq에 대해서 찾아보았다.

heapq 를 사용하면 효율성 개선이 될 수 있다고 생각되었다. 따라서 앞서 내가 말한 방식의 진행 과정은 같지만 heappop을활용해서 최소값을 찾고, 힙구조를 이용하기로 했다.

1. 1차시도
   • 첫번째 시도로 구성한 코드는 효율성테스트를 단하나도 통과하지 못했다. 그래서 while문에 조건을 넣어줘서 최소로 돌려줘야하나? 고민하며 2차 코드를 짰다.
2. 2차시도
   • 효율적이게 잘 짯다고 생각했는데 4개의 히든케이스에서 시간초과가 떴다. 초반에는 2차코드에 문제점을 알지 못했는데, 코드에 써놧듯 나의 코드 자체에 문제가 있었다.
   • 3차시도 후에 코드를 살펴보면서 오류를 찾아냈다. 
   • 2차시도 코드에서 여기가 문제 라고 써있는 부분을 살펴보자.
   • 생각해보니까 answer = -1 하면 while문이 끝나지 않게된다 . 왜냐면 while문조건은 k값보다 작으면 계쏙 돌아가니까! 그래서 return -1로 해서 끊어줘야함을 깨달았다. 
   • 2차 코드 동일하게 쓰고, return -1만 해주면 해당 코드도 정답코드가 된다.
3. 3차코드
   • 2차코드 오류가 나고 왜 오류가 날까 생각해보다가 변수를 너무 많이생성해서 그런가? 하고 변수를 모두 없애본 코드이다.
   • 하지만 역시 그거만 고쳐서는 해결되지 않았다. 왜냐! 2차시도에서 말했던 문제가 같이 발생했기 떄문에 ㅋㅋㅋ
   • 여기서 수정하면서 return -1을 해야한다는 것을 깨달았다... 시간초과 에러를 수정하는게 가장 힘들군 ㅠ

########################################################################
######1차시도 (런타임에러 6개, 효율성테스트 모두 통과 x)
import heapq

def solution(scoville, k):
    answer = 0
    heapq.heapify(scoville)
    while 1:
        minNum = heapq.heappop(scoville)
        if minNum >= k:
            return answer
        else:
            minNum2 = heapq.heappop(scoville)
            heapq.heappush(scoville, minNum + (minNum2*2)) #힙은 pop하면 삭제, 더해서 넣어주는 과정 반복
            answer += 1 #더해주면 결괏값 +1
    
    if scoville[0] > k:
        return answer
    else:
        return -1


##############################################################################
######2차시도 (시간초과 4개, 효율성테스트 모두 통과) --> 해결책 찾음 (return 부분)
import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while scoville[0] < K:
        if len(scoville) > 1:
            minNum = heapq.heappop(scoville)
            minNum2 = heapq.heappop(scoville)
            heapq.heappush(scoville, minNum + (minNum2*2))
            answer += 1
        else:
            answer = -1  ## 👉🏽👉🏽👉🏽👉🏽👉🏽 여기가 문제
    return answer

##############################################################################
##3차시도 -> 혹시 변수가 많아서 그런가 하고 변수없애서 메모리도 줄이고 해봣는데 아님, return이 문제였음
import heapq

def solution(scoville, K):
    heapq.heapify(scoville)
    answer = 0
    
    while scoville[0] < K:
        if len(scoville) > 1:
            heapq.heappush(scoville, heapq.heappop(scoville) + (heapq.heappop(scoville)*2))
            answer += 1
        else:
            return  -1
    return answer

 

다른사람 풀이

https://programmers.co.kr/learn/courses/30/lessons/42626/solution_groups?language=python3&type=all 

프로그래머스

다른사람들의 풀이를 보아하니, 다들 생각한 코드의 진행방식은 같고 모두 heap을 사용해서 풀었다. 내 코드가 결코 안좋은 코드는 아니었기에 기분이 좋았따!