[Python] Programmers 더 맵게

목차

문제

---

https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

 

설계&풀이

---

이전에 백준에서 풀었던 이중 우선순위 큐에서 힙을 사용했기에, 힙 사용법을 대략적으로 파악하고 있어서 큰 어려움은 없었다.

설계는 다음과 같이 했다.

1. scoville 배열만큼 heap 배열에 담아주고, 해당 배열을 heapq로 힙 형태로 전환시켜준다. heappop() 을 사용하면 가장 왼쪽(0번인덱스) 가 추출됨과 동시에 배열에서 삭제 처리 되므로, temp 라는 값에 스코빌 지수를 계산해주고, 나온 temp값을 다시 heappush 해주면 정렬된 상태로 heap이 재구성되므로, while조건까지 계속 돌려주되, 

모든 케이스를 돌았는데도 K이상이 안되면-1을 return 해줘야 하니, 해당 조건을 걸어줬다.

2. 힙의 저장과 삭제 연산은 logN의 시간복잡도를 가집니다. scoville의 길이 N만큼만 반복하기에 시간복잡도는 NlogN 입니다.

레벨 2 치고는 생각보다 그렇게 오래걸리진 않았다.

힙을 몰랐다면 for문을 겁나 돌려서 구하기야 구할 순 있겠지만.. scoville의 길이가 1,000,000 이고 K는 1,000,000,000 까지 늘어나니, 딱 봐도 for문 쓰지 마세요 라는게 보여서 힙을 사용해봤다.

프로그래머스가 문제와 예제 상세설명까지 해줘서 좋은데, 알고리즘 유형을 미리 알려줘서 조금 아쉽다. 실전에선 무슨 유형인지 빠르게 파악하는게 중요하기 때문에, 이런 부분에 대해선 백준이 더 좋은것 같다.

코드 GIT 주소

---

https://github.com/kkkapuq/AlgorithmStudy/tree/main/Python/220610_Programmers_%EB%8D%94%20%EB%A7%B5%EA%B2%8C

GitHub - kkkapuq/AlgorithmStudy: 알고리즘 문제풀이

 

코드

---

'''
1. 최소힙을 이용하고, 힙 안에 있는 원소들이 K이상이라면 for문 종료
2. 힙은 push, pop 할때마다 정렬해주므로.. 맨 처음 원소가 K이상이라면 while문 빠져나오면될듯하다
'''
import heapq

def solution(scoville, K):
    answer = 0
    
    heap = []
    for i in scoville:
        heapq.heappush(heap, i)
        
    while heap[0] < K:
        temp = heapq.heappop(heap) + (heapq.heappop(heap) * 2)
        heapq.heappush(heap, temp)
        answer += 1
        if len(heap) == 1 and heap[0] < K:
            return -1
    
    return answer

 

결과

---

 

구독 및 하트는 정보 포스팅 제작에 큰 힘이됩니다♡