728x90
반응형
문제:
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 *2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.
풀이 방법:
단순하게 scoville 배열을 정렬한 뒤에 첫 번째 인덱스값이 K보다 커지는 순간까지 섞는 과정을 반복하면 된다고 생각했다.
따라서 다음과 같이 코드를 작성할 수 있었다. 중간에 elif 조건으로 scoville 배열이 1인지 확인을 하였는데 이 경우에 더 이상 섞지 못하는 경우이기 때문에 -1을 반환하는 경우인 것이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | def solution(scoville,K): count=0 while(True): scoville.sort() if scoville[0]>K: break elif len(scoville)==1: return -1 else: count+=1 a=scoville.pop(0) b=scoville.pop(0) scoville.append(a+2*b) return count | cs |
하지만 이 방법은 효율성 테스트에서 시간초과로 통과하지 못한다. 이 문제의 태그가 힙(heap)이므로 힙을 사용하도록 코드를 수정하였다.
힙이란 최댓값과 최솟값을 빠르게 찾아내기 위해 고안된 자료 구조로 완전이진트리로 구성되어 있다. 힙에는 최대 힙과 최소 힙 두 가지가 있다. 힙은 부모노드와 자식 노드와만 대소 관계가 존재하는데 부모 노드가 큰 경우가 최대 힙, 자식 노드가 큰 경우가 최소 힙이다.
파이썬에서는 힙 구조를 구현할 수 있도록 모듈을 제공한다. import heapq 로 불러와서 사용을 한다. heapq는 부모 노드가 자식 노드보다 항상 작거나 같은 최소 힙을 제공한다. 따라서 가장 작은 요소가 0 인덱스를 가지며 pop을 했을 경우에 가장 작은 값이 나온다.
이번 문제를 해결하기 위해 heapq.heappush(heap,item)과 heapq.heappop(heap)을 사용했다.
heapq.heappush(heap,item)은 힙의 구조를 유지하면서 heap에 item을 넣는 것이고 heapq.heappop(heap)은 가장 작은 값을 반환하며 이 역시 힙의 구조를 유지한다. 따라서 위의 코드를 heap 구조를 유지하면서 해결하도록 수정하였다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | import heapq def solution(scoville,K): count=0 h=[] for i in scoville: heapq.heappush(h,i) while(True): if h[0]>=K: return count elif len(h)==1: return -1 else: a=heapq.heappop(h) b=heapq.heappop(h) heapq.heappush(h,a+b*2) count+=1 | cs |
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [Programmers]Lv2. 큰 수 만들기 (0) | 2019.02.12 |
|---|---|
| [Programmers]Lv 1. K번째수 (0) | 2019.02.11 |
| [Programmers]Lv 1.같은 숫자는 싫어 (0) | 2019.02.09 |
| [Programmers]Lv 2.조이스틱 (2) | 2019.02.08 |
| [Programmers]Lv 1.문자열 내 마음대로 정렬하기 (0) | 2019.02.07 |