오늘부터 코테를 준비하면서 블로그에 정리하고자한다!
코테를 따로 공부해본 적이 없어서 문제를 풀면서 배워나가려고 한다.
오늘 풀 문제는 더 맵게라는 문제인데,
프로그래머스에서 뭔가 좋은 문제가 없을까 찾다가 제목이 마음에 들어서 골랐다.
나는 매운 걸 좋아하기 때문에...
여튼 본격적으로 문제를 풀어보겠다.
문제
궁극적으로 해야할 일: 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return
일단 처음 든 생각은 일단 정렬을 하고 앞에서 두개를 가져와서 섞고,
섞은 결과를 원래 리스트에 추가하는 걸 반복하면서 조건을 만족하는 지 체크하는 거였다.
def solution(scoville, k):
answer = 0
combined_count = 0
while True:
try:
scoville = sorted(scoville)
minimum = scoville.pop(0)
if minimum >= k:
return combined_count
second_minimum = scoville.pop(0)
combined_scoville = minimum + second_minimum * 2
scoville.append(combined_scoville)
combined_count += 1
except:
return -1
return answer결과는 정확성은 통과했지만 당연히 효율성이 모조리 fail이었다.
근데 위에 보니까 힙을 써서 푸는 문제라는 걸 알 수 있어서 힙에 대해서 공부를 했다.
힙큐란?
특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 사용한다
사용법
import heapqheap= [] // 힙 초기화heapq.heapify(lst) // 리스트를 힙으로 변환heapq.heappop(heap) //힙에서 가장작은 원소 pop, 없으면 에러heapq.heappush(heap, item) // 힙에 item추가이 정도만 알면 된다
최대 힙이라는 것도 있는데, 그건 다른 문제에서 정리하도록 하겠다
이 개념을 알고 다시 코드를 작성했다
import heapq
def solution(scoville, k):
answer = 0
combined_count = 0
heapq.heapify(scoville)
while True:
try:
minimum = heapq.heappop(scoville)
second_minimum = heapq.heappop(scoville)
if minimum >= k:
return combined_count
combined_scoville = minimum + second_minimum * 2
heapq.heappush(scoville, combined_scoville)
combined_count += 1
except:
return -1
return answer기본적인 아이디어는 위에 리스트로 했던거랑 같은데, 힙큐를 쓰니까 확실히 빠르다
결과는 효율성 테스트 모두 통과, 정확성 테스트는 다 통과하다가 16번에서 막혔다..
최종코드
import heapq
def solution(scoville, k):
answer = 0
combined_count = 0
heapq.heapify(scoville)
while True:
try:
minimum = heapq.heappop(scoville)
if minimum >= k:
return combined_count
second_minimum = heapq.heappop(scoville)
combined_scoville = minimum + second_minimum * 2
heapq.heappush(scoville, combined_scoville)
combined_count += 1
except:
return -1
return answer원인이 뭔가 하고 생각해봤는데, 2번째 코드 대로 하면 minimum이 있는데
second_minimum이 없을 경우에 에러가 발생해서 -1이 리턴되게 된다.
그래서 minimum을 구하자마자 그걸 k와 비교해서 k이상이면 지금까지 섞인 횟수를 반환하도록 수정했다
그랬더니 효율성, 정확성 모두 통과되었다!
이번 문제로 뭔가 정렬이 필요하면서 최댓값, 최솟값을 가져와야하는 문제가 있으면 힙큐를 생각해보자라는 생각을 했다
참고
