RUBY

[프로그래머스] 더맵게 본문

PS/Programmers

[프로그래머스] 더맵게

RUBY_루비 2020. 10. 21. 23:59

출처:: 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