happyso
study with happyso
happyso
전체 방문자
오늘
어제
  • 분류 전체보기 (302)
    • GIT (3)
    • 컴퓨터 기본 개념 (29)
    • 알고리즘 (125)
      • 알고리즘 문제 (115)
      • 알고리즘 개념 (10)
    • Go (2)
    • 클라우드 (54)
      • DevOps (4)
      • Kubernetes(쿠버네티스) (33)
      • AWS (6)
      • CKA (8)
    • 리눅스(Linux) (18)
      • 컨테이너(Container) (8)
    • Front (22)
      • JavaScript (2)
      • React (20)
    • Python (21)
      • Python 웹 크롤링 (11)
      • Django (7)
      • MachineLearning (3)
    • 데이터베이스 (6)
      • MariaDB (2)
      • MongoDB (4)
    • C언어 (5)
    • Trouble Shooting (2)
    • 네트워크 (8)
      • CCNA (5)
    • 보안 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • apply
  • 15
  • Patch
  • edit
  • replace
  • kubernetes
  • 18

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
happyso

study with happyso

알고리즘/알고리즘 문제

[python] 프로그래머스 > 힙 > 더 맵게

2021. 2. 27. 01:31

[문제]

1. 문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

2. 제한 사항

  • scoville의 길이는 2 이상 1,000,000 이하입니다.
  • K는 0 이상 1,000,000,000 이하입니다.
  • scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
  • 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

3. 입출력 예

scoville K return
[1, 2, 3, 9, 10, 12] 7 2

 

4. 입출력 예 설명

  1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
    새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
    가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

  2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
    새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
    가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

[풀이]

import heapq

def solution(scoville, K):
    heap = []
    for num in scoville:
        heapq.heappush(heap, num)
    
    answer = 0
    while heap[0] < K:
        answer += 1
        try:
            heapq.heappush(heap, heapq.heappop(heap)+(heapq.heappop(heap)*2))
        except IndexError:
            return -1
    return answer
  • 처음엔 heapq를 사용하지 않고 pop을 사용했다. 역시 통과하지 못했다.
  • heapq를 사용하는 문제였다.
  • heap에 아무것도 들어있지 않는데 heappop을 하려고 할 때 -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

'알고리즘 > 알고리즘 문제' 카테고리의 다른 글

[python] 백준 > DFS > 유기농 배추(1012)  (0) 2021.03.01
[python] 백준 > DP > 피보나치함수(1003)  (0) 2021.03.01
[java, python] 백준 > DP > 다이나믹이 뭐예요?(14494)  (0) 2021.02.26
[python] 백준 > 트리. 재귀 > 트리 순회(1991)  (0) 2021.02.26
[python] 프로그래머스 > 큐/스택 > 프린터  (0) 2021.02.25
    '알고리즘/알고리즘 문제' 카테고리의 다른 글
    • [python] 백준 > DFS > 유기농 배추(1012)
    • [python] 백준 > DP > 피보나치함수(1003)
    • [java, python] 백준 > DP > 다이나믹이 뭐예요?(14494)
    • [python] 백준 > 트리. 재귀 > 트리 순회(1991)
    happyso
    happyso

    티스토리툴바