[프로그래머스] 더 맵게 (python)

문제설명

문제링크: https://programmers.co.kr/learn/courses/30/lessons/42626

---

Idea

1. scoville 함수에서 가장 작은 값과 2번째로 작은 값 추출
2. 문제에 정의된 공식에 의거하여 값을 계산한 뒤 scoville에 추가
3. scoville > K인지 판별
4. scoville > K 조건을 만족하기 위해 몇 번 반복하여 점수 계산을 했는지 반환

---

Solution 01

def solution(scoville, K):
    # 0.503594313
    N = len(scoville)
    scoville.sort()
    for i in range(1, N):
        n1 = scoville.pop(0)
        n = n1 + (scoville[0] * 2)
        scoville[0] = n
        scoville.sort()

        if all([1 if s > K else 0 for s in scoville]):
            return i
    return -1

scoville를 정렬하면 가장 작은 값 순서대로 배열에 정리가 됩니다.

scoville[0]과 [1]에 있는 값을 가져와 문제에 정의된 수식에 의거하여 스코빌 지수를 계산합니다.

계산된 스코빌 지수를 scoville에 다시 정렬합니다. (최솟, 2번째 최솟 값을 0, 1 인덱스에서 가져오기 위해)

만약,

scoville에 있는 모든 값이 K보다 크다면(scoville > K) 이 때까지 스코빌 지수를 계산한 횟수(i)를 반환합니다.

scoville에 있는 모든 값에 대해 스코빌 지수를 계산했지만 여전히 K보다 작다면(scoville < K) -1을 반환합니다.

import timeit
tests = [[[1, 2, 3, 9, 10, 12], 7],
         [[1, 2], 7]]
avg = 0.
for t in tests:
    avg += timeit.timeit(lambda : solution(*t))
print(avg / len(tests))

제가 푼 방식은 대략 0.503초가 걸리는 것으로 파악되었습니다.

프로그래머스 제출시 정확성 테스트는 16/16으로 모두 맞추지만 효율성 테스트에서 0/5 문제가 발생했습니다.

---

Solution 02

Solution 01은 매번 스코빌 지수를 계산할 때 마다 sort와 scoville를 돌면서 scoville > K를 계산합니다.

시간 단축을 위한 방법으로 위에서 언급한 2가지 부분을 줄이기로 판단했습니다.

1. 새로운 스코빌 지수를 넣는 과정
2. scoville 값들이 K보다 큰지 작은지 판별

매번 최솟값을 가져와서 값을 계산하고 계산된 값을 '순서에 맞게' 정렬한 뒤 K보다 큰지 작은지를 판별하기 때문에 scoville를 최소 힙으로 구성하면 모든 조건을 만족하면서 시간을 단축시킬 수 있습니다.

import heapq
def solution(scoville, K):
    # 0.45384143900000007
    N = len(scoville)
    heapq.heapify(scoville)
    for i in range(1, N):
        n1 = heapq.heappop(scoville)
        n2 = heapq.heappop(scoville)
        n = n1 + (n2 * 2)
        heapq.heappush(scoville, n)
        if scoville[0] > K:
            return i
    return -1

scoville 배열을 힙으로 변환합니다.

최솟값과 2번째 최솟값을 각각 pop하여 스코빌 점수를 계산한 뒤 이를 힙에 다시 넣습니다.

최소 힙은 루트노드가 최솟값이니 scoville[0]이 K보다 작다면 scoville 전체가 K보다 작다고 해석할 수 있습니다.

※ 최소 힙 부모노드는 반드시 자식노드보다 작거나 같다는 조건 때문에 (부모노드 <= 자식노드)

따라서 만약,

scoville[0]  > K라면 조건을 만족할 때까지 스코빌 지수를 계산한 횟수(i)를 반환합니다.

루프를 모두 돌았지만 scoville[0] < K라면 문제에 정의된 조건대로 -1을 반환합니다.

import timeit
tests = [[[1, 2, 3, 9, 10, 12], 7],
         [[1, 2], 7]]
avg = 0.
for t in tests:
    avg += timeit.timeit(lambda : solution(*t))
print(avg / len(tests))

위 방식은 대략 0.453초 정도 걸리는 것으로 파악되었습니다.

힙 사용을 통해 기존 0.503초에서 0.453초로 대략 11% 성능 개선이 되어 프로그래머스 문제를 풀었습니다.

전체 코드는 아래 깃허브에서 확인 가능합니다.

https://github.com/daewoonglee/programmers/blob/master/lev2/%EB%8D%94%20%EB%A7%B5%EA%B2%8C.py