상세 컨텐츠

본문 제목

[programmers] 프로그래머스 더 맵게(Python)

Problem Solving/programmers

by HelloMinchan 2020. 6. 19. 04:19

본문

(주)그렙

[programmers] 프로그래머스 더 맵게

(Python)

(글쓴날 : 2020.06.19)

 


* programmers, 프로그래머스 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.


 

 

프로그래머스 더 맵게


1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42626

 

코딩테스트 연습 - 더 맵게

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

programmers.co.kr


2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

매운 음식의 스코빌 지수라는 특정 지수가 주어질 때, 주어지는 모든 음식의 스코빌 지수를 K 이상으로 만드는 문제입니다.

 

저의 경우, 우선순위 큐를 적용하였고, Python을 사용했습니다.

스코빌 지수가 담긴 배열에 최소힙 기반의 우선순위 큐를 적용하여 스코빌 지수가 가장 작은 두 음식이 K 미만일 경우 문제에서 제시한 방법으로 섞은 뒤, 다시 우선순위 큐에 저장하고 꺼내는 것을 반복하여 문제를 해결했습니다.


3) 코드

 

* Python 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import heapq
 
 
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
 
    while 1:
        if len(scoville) == 1:
            if scoville[0>= K:
                return answer
            return -1
 
        spicy1 = heapq.heappop(scoville)
        spicy2 = heapq.heappop(scoville)
 
        if spicy1 < K or spicy2 < K:
            newSpicy = spicy1 + (spicy2 * 2)
            heapq.heappush(scoville, newSpicy)
            answer += 1
        else:
            return answer

 

관련글 더보기

댓글 영역