프로그래머스 - 더 맵게

자세한 설명은 링크 참고

가장 맵지 않은 2개의 요소를 ([0]+([1]*2)의 연산을 하여 모든 요소를 K이상으로 만드는데 걸리는 연산 횟수를 리턴하는 문제이다.

일단 코드부터

def solution(scoville, K):
    st = sorted(scoville)
    cnt = 0
    while True :
        if st[0] == 0 and st[1] == 0 :
            answer = -1
            break
        elif len(st) == 1 :
            answer = -1
            break
        else :
            st.append(st[0] + (st[1] * 2))
            del st[:2]
            st.sort()
            cnt += 1
            if st[0] > K :
                answer = cnt
                break
            else :
                continue
    return answer

먼저 제한 사항이 될만한 K를 넘을수 없을 것이라 판단된 것을 제외해주었다.
이후 주어진 리스트를 sorted()하여 정렬하여 준 뒤
연산을 진행하고
연산에 사용한 요소를 제거해 주고
다시 sort()로 정렬해주는 것을
0번째 요소가 K이상이 될때까지 반복하였다.
결과는
효율성 0점이다. 아마 sort()가 시간복잡도가 높다고 하던데 그걸 빼면 되지 않을까 해서 다시 코드를 짜보았다.

def solution(sco, K):
    cnt = 0
    while True :
        min0 = min(sco)
        sco.remove(min0)
        min1 = min(sco)
        sco.remove(min1)
        sco.append(min0 + (min1 * 2))
        cnt += 1
        if min(sco) > K :
            answer = cnt
            break
        elif min(sco) == 0 or len(sco) <= 1 :
            answer = -1
            break
        else :
            continue
    return answer

뭔가 조잡한 느낌이.. min()함수에는 2개의 요소를 반환하는 파라미터는 없어서 최소값을 지워주고 다시 받아왔다.
결과는
동일한 점수로 실패

하지만 문제는 시간이 더 걸렸다는 것이다. 어쩌지..
질문하기에 들어갔더니 heapq라는 모듈이 있다는 것을 알게 되었다.
이에대한 정보는 이 블로그에 있다.
다시 코드를 짜보자

import heapq

def solution(st, K):
    answer = 0
    heapq.heapify(st)
    cnt = 0
    while True :
        if st[0] == 0 and st[1] == 0 or len(st) == 1:
            answer = -1
            break
        else :
            hq0 = heapq.heappop(st)
            hq1 = heapq.heappop(st)
            st.append(hq0 + (hq1 * 2))
            cnt += 1
            if st[0] > K :
                answer = cnt
                break
            else :
                continue
    return answer

논리상 바뀐건 없다.
하지만 heapq모듈을 사용한 후에 연산속도가 매우 빨라진걸 확인할 수 있었다.