힙

<프로그래머스 고득점kit>

<더 맵게>

import heapq
def solution(scoville, K):
    heapq.heapify(scoville)
    count=0
    while len(scoville)>=2:
      min=heapq.heappop(scoville)
      if(min>=K):
        return count
      else:
        min2=heapq.heappop(scoville)
        heapq.heappush(scoville,min+(min2*2))
        count+=1
    print(scoville)
    if(scoville[0]<K):
      return -1
    return count

<해설>

완전탐색으로 구현할 시간복잡도가 O(n^2)이 되기때문에 힙구조를 통해 시간을 줄인다.먼저 힙구조로 정렬이 되면 가장 O(nlog(n))이 되고 아래서부터 최하위값을 빼면서 끝까지 탐색해나가서 결국 탐색부분도 O(nlog(n))이되어 전체 시간복잡도는 O(nlog(n))이된다.전체적인 로직은 먼저 최하위값만 찾고 만약 그값이 K지수보다 크거나 같다면 바로 탈출하고, 그것이 아니라면 두번째로 덜매운것을 섞어야 하기때문에 최하위를 추출한 힙에서 하나 더 추출하여 둘이 공식을 통해 더하고 scoville에 힙메서드로 끼워넣어 위치시킨다.

예외사항:한번 섞을 때 두개를 추출해내기에 만약 scoville의 길이가 2보다 작다면 런타임에러가 나서 반복조건은 len(scoville)>=2로 설정하고 배열의 끝까지 섞어가며 K보다 크거나 같은 것이 안나온다면 마지막에 하나가 남고 그 하나를 따로 조거문을 통해 반환한다.

<타겟 넘버>

def solution(numbers, target):
    superNode=[0]
    for number in numbers:
      subNode=[]
      for value in superNode:
        subNode.append(value+number)
        subNode.append(value-number)
      superNode=subNode
    return superNode.count(target)

<해설>

주어진 연산의 종류가 +,-이므로 numbers로 만들 수 있는 모든 경우의 수를 구해보면 2^5나오고 이는 BFS(넓이우선탐색)방식을 통해 구현 할 수 있다.먼저 수퍼노드를 설정해놓고 초깃값은 0으로 넣는다.그리고 주어진 numbers를 탐색하여 더하고 뺄 숫자를 알아내고 현재의 superNode를 탐색하여 subNode에 미리 append를 통해 계산된 경우의 수들을 담고,담는 과정이 끝나면 superNode에 subNode로 최신화시킨다.같은 레벨에서 탐색해나가기에 BFS라 볼 수 있다.