데이터사이언스 기록기📚

[프로그래머스] Level 2_더 맵게(힙) 본문

Coding Test/프로그래머스(Python)

[프로그래머스] Level 2_더 맵게(힙)

syunze 2022. 9. 25. 17:23

📌문제 유형

힙(Heap)

 

📌문제

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

📌나의 문제풀이

1차시도(정확성: 66.7, 효율성: 0, 합계 : 66.7)
def solution(scoville, K):
    answer = 0
   
    while scoville[0] < K:
        # 스코빌 계산 후 값 넣기, 만든 값 삭제
        new_score = scoville[0] + scoville[1] * 2
        scoville.append(new_score)
        scoville = scoville[2:]
        
        # 스코빌 만든 횟수 
        answer += 1
        
        # 스코빌 정렬
        scoville.sort()
        
        # 스코빌 만들 수 없는 경우 -> -1 내뱉기
        if len(scoville) == 1:
            if scoville[0] < K:
                return -1
            
    return answer
2차시도(정확성: 성공, 효율성:0, 합계: 76.2)
import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville) # 최소값만 유효!!, 미리 생성한 리스트 힙 자료형으로 변경
    
    while scoville[0] < K:
        new_num = 0
        min_num = heapq.heappop(scoville)
        heapq.heapify(scoville)
        second_num = heapq.heappop(scoville)

        new_num = min_num + second_num * 2
        heapq.heappush(scoville, new_num)
        answer += 1
        
        if len(scoville) == 1 and scoville[0] < K:
                return -1
    
    return answer
3차 시도(통과)
  •  heapq 사용
    • heappop 사용하여 가장 작은 값, 두 번째 작은 값 찾기 -> 계산
    • 스코빌 계산 후 넣기
    • 스코빙 K이상으로 만들 수 없는 경우 -1 리턴
import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville) # 최소값만 유효!!, 미리 생성한 리스트 힙 자료형으로 변경
    
    while scoville[0] <= K:
        new_num = 0
        # 스코빌 계산 숫자 찾기
        min_num = heapq.heappop(scoville)
        second_num = heapq.heappop(scoville)
        
        # 스코빌 계산 후 넣기
        new_num = min_num + second_num * 2
        heapq.heappush(scoville, new_num)
        answer += 1
        
        if scoville[0] < K:
            # 스코빌 지수 K이상으로 만들 수 없는 경우
            if len(scoville) == 1:
                return -1
            else:
                continue
        else:
            return answer

 

📌다른사람들 풀이

1) 나의 풀이와 유사

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

2) 간단한 풀이

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

 

📌리뷰

 - 힙(heap) : 특정한 규칙을 가지는 트리

  • 최댓값과 최솟값을 찾는 연산일 때 사용!
  • 키 값의 대소관계는 부모-자식간에만 성립, 형제 노드 사이에서는 대소 관계 성립하지 않는다.

 

 

📌참고

- heapq 정리

 

[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기

힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다. 힙 property : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대

littlefoxdiary.tistory.com

 

728x90
Comments