[프로그래머스] 더 맵게 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

효율성 테스트에서 시간 초과가 발생하는 것을 막고 빠른 연산 수행을 위해 heap 자료구조를 사용한다.

 

1. heap 자료구조를 사용하기 위해 heapq 모듈을 불러온다. import heapq
2. 리스트 형식을 입력받아진 scoville 자료를 heap 자료구조로 바꿔준다. heapq.heapify(scoville)
3. scoville의 제일 작은 값이 K보다 작으면 반복해야 연산을 해야 하는데 이때 제일 작은 값을 찾겠다고 min() 함수를 사용하면 시간이 많이 소모된다.
4. 여기서 heapify()는 기본적으로 최소 힙 정렬이 되기 때문에 정렬한 scoville의 제일 앞 원소의 값이 K보다 작으면 반복하도록 구현하면 시간이 단축된다. while (scoville[0] < K)
5. 만약 scoville 원소이 개수가 2개가 안된다면 if (len(scoville) <= 1)
6. 모든 음식의 스코빌 지수를 K이상으로 만들 수 없기 때문에 -1을 반환한다. return -1
7. scoville 원소의 개수가 2개 이상이라면 제일 작은 원소를 삭제함과 동시에 가져오고 v1 = heapq.heappop(scoville)
8. 그다음으로 작은 원소를 삭제함과 동시에 가져온다. v2 = heapq.heappop(scoville)
9. 가져온 각 값을 가지고 새로운 스코빌 지수를 계산하여 값을 추가한다. heapq.heappush(scoville, v1 + v2 * 2)
10. 두 음식을 섞는 연산이 수행되었으므로 섞은 횟수를 1 증가시킨다. answer += 1

반응형

3. 소스코드

import heapq

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

    return answer