Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 안드로이드
- opic
- fibo
- 영어회화
- 오픽
- 주석
- 메모이제이션
- ㅂ
- 안드로이드주석
- 오픽가격
- topdown
- dynamicProgramming
- 디피
- dp
- XML주석
- English
- 오픽공부법
- 오픽노잼공부방법
- 오픽노잼
- stack 스택
- 탑다운
- 오픽점수잘받는방법
- 영어말하기
- 다이나믹프로그래밍
- 바텀업
- XML
- 이진탐색 #나무 자르기
- 이진탐색
- 피보나치수열
Archives
RUBY
[프로그래머스] 더맵게 본문
출처:: programmers.co.kr/learn/courses/30/lessons/42626#
분류:: 힙
1. 문제 이해 및 해결과정
2. 풀이방법
1. [ python ] heap
- heap을 이용하면 따로 정렬하는 과정이 필요없음
import heapq
def solution(scoville, K):
cnt = 0
hq=[]
for x in scoville: #힙큐
heapq.heappush(hq,x) #정렬과정이 필요없음
while hq:
if hq[0]>=K: #현재힙에서 제일 작은수가 k보다 크면
break
elif len(hq)==1: #힙의 길이가 1이면, 원소 2개를 뺄 수 없음
return -1
else:
b=heapq.heappop(hq) #힙구조에서 제일작은 수 빼기
a=heapq.heappop(hq) #힙구조에서 작은 수 빼기
heapq.heappush(hq,2*a+b)
cnt+=1
return cnt
3. 오답원인
1. 시간초과
- 매번 정렬해야하므로 n*logn
def solution(scoville, K):
cnt = 0
sco=sorted(scoville,reverse=True)
if sco[-1]>=K: #이미 모든 스코빌 지수를 만족하는 경우
return cnt
while len(sco)>=2:
if sco:
b=sco.pop()
a=sco.pop()
sco.append(2*a+b)
sco.sort(reverse=True)
cnt+=1
if sco[-1]>=K:
break
if sco[-1]<K: #모든음식의 스코빌지수 만들 수 없는 경우
cnt=-1
return cnt
2. 1번의 개선 코드 - 시간초과
def solution(scoville, K):
cnt = 0
while scoville:
scoville.sort(reverse=True)
if scoville[-1]>=K:
break
elif len(scoville)==1:
return -1
else:
b=scoville.pop()
a=scoville.pop()
scoville.append(2*a+b)
cnt+=1
return cnt
4. 알게된 점
'PS > Programmers' 카테고리의 다른 글
[프로그래머스] 구명보트 (0) | 2020.10.22 |
---|---|
[프로그래머스] 프린터 (0) | 2020.10.21 |
[프로그래머스] 소수 찾기 (0) | 2020.10.21 |
[프로그래머스] 가장 큰 수 (0) | 2020.10.20 |
[프로그래머스] 주식가격 ★ (0) | 2020.10.16 |
Comments