[코딩연습6일차] 프로그래머스 : 더 맵게 / python

오늘은 놀고 돌아왔기 때문에 반성삼아 lv.2문제를 풀어보았따!!!

코딩연습에 재미를 붙였다 생각했는데 아직 6일차라니ㅋㅋㅋ 분발해야겠다.

그래도 놀고와서 스트레스 다 풀렸으니까 앞으로 화이팅 🎈😚

---

 

문제 설명

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

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

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

제한 사항

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

입출력 예

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

입출력 예 설명

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회입니다.

---

내 1차 답>>

 

def solution(scoville, K):
    answer = 0

    while min(scoville) < K and len(scoville)>=2:
        scoville.sort()
        i = scoville.pop(0) + scoville.pop(0)*2
        scoville.append(i)
        answer += 1
        
        if min(scoville) > K:
            break
        elif min(scoville) <K and len(scoville)<2:
            answer = -1
            break
    return answer

 

1. scoville의 최소값이 K보다 작고 길이가 2이상이면, 

2. scoville을 오름차순 정렬해주고, 수식 대로 i를 만든뒤 배열에 추가. answer은 1씩 증가.

3. 최솟값이 K보다 커지면 break

4. 최소가 K보다 작은데 원소의 갯수가 2미만이면 조합을 만들 수 없으니 -1, break

 

정확도는 맞는데 효율성이0!

얘는 아마 sort()를 while문 안에서 계속 때려줘야하니까 그런가보다.

---

2차 시도 (정답) >> heapq라는 함수를 써줌!

얘는 'heap'이라는 이진트리 안에 자료를 저장하는데,

""부모노드 <= 자식노드""의 알고리즘을 가지고 있기 때문에 얘는 무조건 자료를 오름차순 정렬한다.

 

import heapq
    
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
        
    while scoville[0] < K and len(scoville)>=2:
        heapq.heappush(scoville, heapq.heappop(scoville) + heapq.heappop(scoville)*2)
        answer += 1
        
        if scoville[0] > K:
            break
        elif scoville[0] <K and len(scoville)<2:
            answer = -1
            break
    return answer

 

1. heapq.heapify를 통해 scoville을 heap형태의 자료로 저장해준다.

2. (이미 오름차순 된 자료이기 때문에) scoville[0] = 최솟값... 나머지 로직은 아까와 같음.

3. 효율성까지 통과~~ 끝!!

 

 

참조: python.flowdas.com/library/heapq.html

heapq --- 힙 큐 알고리즘 — 파이썬 설명서 주석판

참조2: programming119.tistory.com/85

[Python] 파이썬 Heapq 모듈 사용하기 / 힙(Heap) 구조