[프로그래머스] 더 맵게

2022. 3. 2. 18:27· 개발/알고리즘
반응형

min heap에서 2가지 원소를 pop 하고 a + 2 * b 의 등식을 적용 후 push 하는 문제였다.

파이썬의 heapq를 처음 사용해보았다.

  • 파이썬의 heapq의 경우 일반 리스트를 min heap 처럼 사용할 수 있게 해주는 라이브러리이다.
  • heapq.heapify(list): list가 min heap으로 변한다. (O(N), 제자리에서 정렬)
  • heapq.heappop(list): heapify된 list에서 min 값을 리턴.
  • heapq.heappush(list, item)
    • push의 경우 이론에서 배웠던 heapify를 자동으로 수행해준다.
    • 0번 인덱스에는 가장 작은 값, n번 인덱스의 2n + 1 인덱스에는 left child, 2n + 2 인덱스에는 right child ( parent <= left, right child )
import heapq
import collections
def solution(scoville, K):
    c = collections.Counter(scoville)

    # 기존 리스트를 힙으로 변환
    heapq.heapify(scoville)

    # 우리가 원하는 맵기까지 만들지 못하고, 힙의 길이가 2 이상인 경우 새로운 음식 만들기.
    cnt = 0
    while scoville[0] < K and len(scoville) >= 2:
        smallest = heapq.heappop(scoville)
        next_small = heapq.heappop(scoville)
        heapq.heappush(scoville ,smallest + 2 * next_small)
        cnt += 1

    # 힙의 길이가 1이 되어버리고, 원하는 맵기까지 도달 못한 경우
    if len(scoville) < 2 and scoville[0] < K:
        return -1

    return cnt

 

 

효율성 테스트

 

테스트 1 〉 통과 (191.62ms, 23.8MB)
테스트 2 〉 통과 (382.37ms, 37.5MB)
테스트 3 〉 통과 (2037.07ms, 80.1MB)
테스트 4 〉 통과 (152.45ms, 22.2MB)
테스트 5 〉 통과 (2082.18ms, 82.2MB)
반응형
저작자표시 비영리 동일조건 (새창열림)

'개발 > 알고리즘' 카테고리의 다른 글

[프로그래머스] 주식가격  (0) 2022.03.02
[프로그래머스] 프린터  (0) 2022.02.28
[프로그래머스] 기능개발  (0) 2022.02.28
[프로그래머스] 다리를 지나는 트럭  (0) 2022.02.28
'개발/알고리즘' 카테고리의 다른 글
  • [프로그래머스] 주식가격
  • [프로그래머스] 프린터
  • [프로그래머스] 기능개발
  • [프로그래머스] 다리를 지나는 트럭
Woogie2
Woogie2
창업, 개발, AI
반응형
Woogie2
Dev In Seoul
Woogie2
전체
오늘
어제
  • Dev in Seoul (47)
    • 개발 (39)
      • 알고리즘 (5)
      • 오늘 배운 지식 (24)
      • 학교 수업 (9)
    • 경험, 생각, 일상 (1)
      • 스타트업 (0)
    • 학교 (2)
    • Machine Learning (5)
      • AI (4)
      • 논문 리뷰 (1)

인기 글

최근 글

최근 댓글

hELLO · Designed By 정상우.v4.2.2
Woogie2
[프로그래머스] 더 맵게
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.