[프로그래머스] 더 맵게- python (레벨 2)

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

코딩테스트 연습 - 더 맵게

풀이

문제를 보았을때 알수있는 힌트

단순하게 생각하면 정렬을 하고 최소 값 두개를 뽑아서 조건에 맞는 식을 다시 집어넣고 정렬하고 하면 문제는 풀수있다.

# 단순하게 리스트로 풀었을 경우

def solution(scoville, K):
    answer =0
    count=0
    scoville.sort()
    while scoville[0]<K :
        if len(scoville)<2:
            count=-1
            break
        v1=scoville.pop(0)
        v2=scoville.pop(0)
        temp = v1+(v2*2)
        scoville.append(temp)
        scoville.sort()
        count+=1
    answer = count
    
    return answer

이렇게 푼다면 정확성은 100%로 이상없었지만 효율성은 시간 초과가 난다.

scoville의 최대가 10의 6승인데 그것을 계속 정렬을 하고있기 때문에 엄청난 시간이 소요된다.

이럴때는 O(nlogn) 인 힙큐를 이용하여 문제를 풀면 효율성을 해결 할 수 있다.

 

import heapq
def solution(scoville, K):
    h = []
    count=0
    # 처음 우선 순위 큐에 집어 넣기
    for i in scoville:
        heapq.heappush(h,i)
    # 최소가 K 이상 이 나올 때까지 돌린다.
    while h[0]<K :
        # 우선순위큐의 리스트가 2보다 작은 경우 -1로 출력
        if len(h)<2:
            count=-1
            break
        # 최소인 힙을 두개 꺼낸다.
        v1= heapq.heappop(h)        
        v2= heapq.heappop(h)
        # 최소인 두개의 값을 조건에 맞게 섞는다
        temp = v1+(v2*2)
        # 섞은 값을 다시 우선순위 큐에 집어 넣는다.
        heapq.heappush(h,temp)
        count+=1
    
    answer = count
    
    return answer

https://github.com/dydwkd486/coding_test/blob/main/programmers/더%20맵게.py 

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리