더 맵게
레벨2, 힙
작년에 프로그래밍을 처음 시작하고, 처음으로 접했던 프로그래머스 레벨 2 문제였습니다.
당시에는 heap이 뭔지도 몰랐기에.. 분명 논리적으로 맞는데, 계속 시간초과가 나서 정말 미치는줄 알았습니다. 그러다 결국 포기했었던 기억이 있는 문제입니다
1. 문제 설명
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다.
모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.
문제의 요구사항은 매우 간단합니다. 가장 안 매운 음식을(작은 수) 두 가지를 뽑아, 이를 조합해 조금 더 매운 음식(더 큰 수)을 만드는 행동을 반복해서, 최소 K만큼은 매운 음식을 만들어야 합니다.
2. 제한사항
1. scoville의 길이는 2 이상 1,000,000 이하입니다.
2. K는 0 이상 1,000,000,000 이하입니다.
3. scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
4. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
3. 사고과정 / 나의 풀이
처음에는 조합 전, 조합 후 2개의 리스트를 가지고 문제를 풀 생각이었습니다. 그렇지만, 조금 생각 해 보니, [1, 1, 2, 2, 2, 9] 같은 경우 조합 후에는 리스트가 [3], [2, 2, 2, 9] 이 되고 한 번 더 조합하면 [3, 6], [2, 9]이 되는 등, 생각보다 비교 로직이 많아진다(귀찮아진다)는 생각에 그냥 하나의 리스트만 사용하기로 했습니다.
그래서 가장 단순하게 생각 해 본 절차는
1. 내림차순으로 정렬한다.
2. 2개를 pop한다.
3. 결과를 append한다.
4. 횟수를 +1 한다
5. 이를 조건이 만족할 때 까지 반복한다.
이를 가장 단순하게 표현한 코드는 아래와 같습니다.
def solution(scoville, K):
answer = 0
while min(scoville) < K:
scoville.sort(reverse=True)
a = scoville.pop()
b = scoville.pop()
new = a + 2 * b
scoville.append(new)
answer += 1
return answer
논리적으로는 틀릴 이유가 없는 풀이라고 생각해서 제출 해 보니, 역시 정확성은 통과... 일 줄 알았는데 런타임 에러가 꽤 많이 났습니다.
물론 당연하게도 효율성은 0점이 나왔습니다.
조금 생각 해 보니, pop이 연달아 있는것이 문제인 것 같습니다. 그래서 가장 단순하게 try - except문을 활용 해 봤습니다.
def solution(scoville, K):
answer = 0
while min(scoville) < K:
try:
scoville.sort(reverse=True)
a = scoville.pop()
b = scoville.pop()
new = a + 2 * b
scoville.append(new)
answer += 1
except:
return -1
return answer
결과적으로 정확성은 모두 통과했습니다. 그러나 역시나 효율성은 0점입니다.
왜일지 코드를 확인 해 보면, while문을 순회하며 매번 sort를 하게됩니다.
아무리 파이썬 기본 sort가 빠르다지만(상대적으로), 역시 O(nlogn)의 벽은 높습니다. (참고: 파이썬 시간복잡도 정리)
문제풀이 페이지에 남아있는 풀이를 보니, 이전에는 여기까지 왔다가 포기한 것 같았습니다.
그렇지만 이제는 힙에 대해서 이해했고, 써먹을 줄도 알게 되었기에, 아래와 같이 코드를 수정 해 줍니다.
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville)
while scoville[0] < K:
try:
a = heapq.heappop(scoville)
b = heapq.heappop(scoville)
new = a + b + b
heapq.heappush(scoville, new)
answer += 1
except:
return -1
return answer
가장 큰 다른점은, 힙의 구조상 pop, push가 반복되어도 정렬을 매번 할 필요가 없다는 점이겠고, 이로인해 효율성이 매우 높아집니다.
따라서 최초에 heapify 한 번만 해주면 정렬은 신경 쓸 필요가 없게 됩니다.
3. 다른 사람의 풀이
가장 먼저 보이는 풀이
import heapq as hq
def solution(scoville, K):
hq.heapify(scoville)
answer = 0
while True:
first = hq.heappop(scoville)
if first >= K:
break
if len(scoville) == 0:
return -1
second = hq.heappop(scoville)
hq.heappush(scoville, first + second*2)
answer += 1
return answer
제 마지막 풀이와 거의 비슷한데, 다만 while문에 조건을 거는 대신, 탈출조건으로 이를 처리했습니다. 이후에 커뮤러닝 강사님께서도 말씀하셨다시피, 간략하게 풀이 할 때에는 탈출조건을 활용하는 것이 가장 편리 한 것 같습니다.
from heapq import heapify, heappush, heappop
def solution(scoville, K):
heapify(scoville)
for i in range(1000000):
try:
heappush(scoville, heappop(scoville)+(heappop(scoville)*2))
if scoville[0] >= K: return i+1
except:
return -1
처음에 보고는 가장 의문이 많이 들었던 코드였습니다. 아무래도 이유는 for문을 활용했다는 점과, range에 저렇게 무심한듯 숫자로 박아넣은 부분, 두 가지가 그 원인이 아닐까 싶은데, 생각해보면 가장 영리한 풀이가 아닐까 싶습니다.
굳이 answer+=1 같은 코드도 활용하지 않고 i로 모두 해결 해 버렸으며, 문제의 조건에서 길이도 1,000,000으로 제한되어있으니 딴지를 걸 수 없겠습니다. 부족한 지식을 어찌 쥐어짜서 꼬투리를 잡아봐도 결국은 가독성 말고는 흠잡을 곳이 없어보입니다.
