[프로그래머스/파이썬/Level 2] 42626번 더 맵게

[프로그래머스/파이썬/Level 2] 42626번 더 맵게

프로그래머스의 완주하지 못한 선수 문제와 마찬가지로 코드를 구현하는 데는 오래 걸리지 않았다.

혹시 연산량을 줄일 수 있을까 해서 이미 스코빌지수가 K이상인 요소들을 제외하고 새로운 리스트(new)를 만들었다.

또한 오름차순으로 정렬하고 제일 작은 수와 두 번째로 작은 수를 인덱스 번호를 이용하여 가져오고

두 개의 수를 섞어 새로운 스코빌 지수를 추가해준다.

만약 제일 작은 수가 스코빌지수가 K이상이 된다면 반복문을 멈추고, 더 이상 섞을 수 없을 경우에는 -1을 출력한다.

하지만 효율성 테스트에서 마찬가지로 시간 초과 문제가 나타났다.

#----- 시간초과 def solution(scoville, K): answer = 0 new = [] # 스코빌 지수가 K 미만인 경우, 새로운 리스트(new)에 추가 for s in scoville: if s <= K: new.append(s) while True: # 오름차순 정렬 new.sort() # 제일 작은 수가 K이상이면 반복문 멈춤 if new[0] >= K: break # 더이상 섞을 수 없을 경우(요소가 1개인 경우) -1을 출력 if len(new) == 1: return -1 min1 = new.pop(0) # min1 : 제일 작은 수 min2 = new.pop(0) # min2 : 두번째로 작은 수 # 새로운 스코빌 지수 추가 new.append(min1 + (min2 * 2)) answer += 1 return answer

문제에 나와있는 heap 자료구조를 찾아보니 모든 부모 노드가 자식 노드보다 작거나 같은 값을 가지는 이진트리 구조이다.

데이터를 입력하면 자동으로 오름차순으로 정렬되기 때문에 기존 연산량보다 줄어든다.

heap 자료구조는 처음 접해봐서 아래의 공식문서를 참고하여 코드를 작성했다.

import heapq def solution(scoville, K): heap = [] answer = 0 # 스코빌 지수 리스트를 힙자료구조로 변경 for s in scoville: heapq.heappush(heap, s) while True: # 최소값이 기준 K이상인 경우 반복문 멈춤 if heap[0] >= K: break # 더 이상 섞을 수 없는 경우 -1을 출력 if len(heap) == 1: return -1 min1 = heapq.heappop(heap) # min1 : 제일 작은 값 min2 = heapq.heappop(heap) # min2 : 두번째로 작은 값 # 새로운 스코빌 지수 추가 heapq.heappush(heap, min1 + min2 * 2) answer += 1 return answer

from http://data-study-blog.tistory.com/22 by ccl(A) rewrite - 2021-08-29 00:26:10