더 맵게
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
- 내 풀이
- 테스트케이스는 통과 / 효율성 테스트- 시간초과
- heapq 사용
[Python] heapq 모듈
heap 힙은 최댓값과 최솟값을 빠르게 찾아내기 위한 자료구조 우선순위 큐를 구현하기 위한 자료형 heap은 list 기반으로 동작 heap의 root가 가장 작은 값을 가지는 최소힙 heapq Python에서는 heap 자료
yygs321.tistory.com
import heapq
def solution(scoville, K):
heapq.heapify(scoville)
sum=0
answer = 0
while min(scoville)<K:
if len(scoville)<2:
return -1
min1=heapq.heappop(scoville)
min2=heapq.heappop(scoville)
sum=min1+min2*2
heapq.heappush(scoville,sum)
answer+=1
return answer
- ⚠️min(scoville)값을 찾기 위해 전체 배열을 탐색해서 생기는 문제
- → scoville[0] 하면 바로 최솟값 나옴
- 코드 수정
import heapq
def solution(scoville, K):
heapq.heapify(scoville)
sum=0
answer = 0
while scoville[0]<K:
if len(scoville)<2:
return -1
min1=heapq.heappop(scoville)
min2=heapq.heappop(scoville)
sum=min1+min2*2
heapq.heappush(scoville,sum)
answer+=1
return answer
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] [Level 2] [완전탐색] 피로도 (0) | 2022.08.12 |
|---|---|
| [프로그래머스] [Level 2] [완전탐색] 소수 찾기 (0) | 2022.07.28 |
| [프로그래머스] [Level 2] [스택/큐] 프린터 (0) | 2022.07.23 |
| [프로그래머스] [Level 2] [스택/큐] 기능 개발 (0) | 2022.07.23 |
| [프로그래머스] [Level 2] [해시] 위장 (0) | 2022.07.21 |