스코빌 지수

코딩테스트 연습 - 더 맵게

프로그래머스의 코딩테스트 연습에서 카테고리를 잘 보면 사용해야 하는 자료 구조가 적혀 있다. 이번에 하게 된 것은 힙(Heap) > 더 맵게 이다. 작은 수와 그 다음 작은 수를 사용해서 연산을 하고 다시 리스트에 넣어서 최소값 기준에 대한 조건만 맞추면 되겠다 싶었으나 효율성에서 과감히 아웃당했다. 그렇다면 왜 여기서 '힙'을 제시한 걸까?

 

스택 구조를 사용하면 안되는 걸까?

def solution(scovile, k):
    answer = 0 
    while min(scovile) < k :
        if len(scovile) == 1 :
            answer = -1 
            break;

        index = scovile.index(min(scovile))

        first_min = scovile.pop(index)
        index_two = scovile.index(min(scovile))
        second_min = scovile.pop(index_two)
        new_food = first_min + (second_min * 2)
        
        scovile.append(new_food)        
        answer += 1
    
    return answer

파이썬에서는 리스트를 스택 구조처럼 사용할 수 있게 해주는 메소드가 존재한다. 스택 구조는 마지막에 들어간 데이터가 가장 먼저 나오는 구조를 가지고 있다. 입구가 하나밖에 없는 구조에 데이터를 넣고 뺀다고 생각하면 쉽다.

 

list.pop([i])

이 메소드는 i 번째 인자를 제거하는 동시에 그 값을 리턴하기 때문에 다른 변수에 대입하여 사용 가능하다. 위 표현은 파이썬의 document를 참고한 것인데 중괄호를 적어야 함을 말하는 것이 아니라 i라는 인덱스를 적어도 되고 안 적어도 되는 옵셔널 값이라는 뜻이다. 인덱스를 적지 않으면 제일 마지막에 있는 값을 삭제하는 동시에 리턴한다. 

 

list.append(x)

append 메소드는 list에 값 x를 마지막 인덱스에 추가한다. 

 

pop()과 append() 메소드를 적절히 사용하면 스택 구조와 같이 마지막 인덱스에서 데이터를 추가하고 꺼낼 수 있다. 이제 내가 작성한 코드를 보면 pop() 메소드와 min() 메소드를 사용해서 값을 반환 받은 것을 알 수 있다. 작은 값을 찾는 정렬이 수행되야 하고 그 인덱스를 이용해서 값을 반환 받기 때문에 스택을 이용한 것도 아니게 된다.  

 

정확성 테스트는 모두 통과했지만 효율성 테스트에서는 시간 초과로 모두 실패하고 말았다. 여기서 최소값을 구하기 위해 리스트 내부에서 정렬이 들어간다. 이 최소값이 제시된 k의 값 이상이 될 때까지 while문을 반복하므로 긴 리스트가 들어오면 시간 효율성 측면에서 실패하는 것이다. 

그렇다면 왜 처음에 이 문제는 '힙' 카테고리로 분류 되었을까?

 

스택 말고 큐

큐는 선입선출의 대표적인 자료구조이다. 처음 추가된 데이터를 처음으로 반환 받을 수 잇다. enqueue는 데이터 입력을, dequeue는 데이터 출력을 의미하며 이 또한 list를 통해서 구현 가능하다. 큐 라이브러리를 사용하려면 collections.deque 모듈을 사용하면 된다.

from collections import deque

그러나 사용시 주의해야 할 부분이 있다. 우선 데이터를 리스트의 끝에서 추가하고 삭제하는 것은 빠르지만, 리스트의 앞 부분에서 추가하고 삭제하는 것은 느리다. 리스트의 앞 부분에서 바꿔 준다면 각 인덱스에 있는 요소들의 위치를 앞으로 한칸 씩 이동하거나 혹은 뒤로 밀어야 하는  상황이 있기 때문에 느리게 동작하는 것이다. 

이 문제에서 필요로 하는 것은 작은 값을 찾는 것이다. 두개의 작은 값을 찾아서 연산을 통해 더 큰 값을 만들어 낸다. 여기서 생각나는 것은 바로 '힙'!

 

파이썬의 힙은 작은 값 부터 정렬되는 우선순위 힙

파이썬에서는 힙 큐 알고리즘을 구현한 heapq.py 라는 모듈을 제공한다. 일반적으로 접하는 힙 배열은 값이 크고 인덱스는 작은 값을 가지는 노드 순으로 표시된다. 그러나 파이썬에서 제공하는 힙은 그 반대라고 보면 된다. heapq에서 제공하는 메소드 몇 가지를 알아보면 다음과 같다. 

 

heapq.heappop(heap)

이 메소드는 힙에서 가장 작은 값을 삭제한 뒤 리턴한다. 이때 리스트의 pop과는 다르게 pop을 하고 난 뒤에도 힙의 구조를 유지하는 것이다. 따라서 heappop을 통해서 가장 작은 값 두개를 반환 받기 위해 연속적으로 pop을 두 번 사용해도 힙 구조가 유지 되는 것이며 이는 앞서 작성한 코드에서 min() 을 통해 최소값을 찾기 위해 정렬을 시도하는 일이 없어도 된다는 것을 의미한다. 

여기에 더 좋은 메소드가 존재한다.

 

heapq.heappushpop(heap, item)

item을 heap에 추가시키는 메소드이다. 이를 적절히 사용해서 연산을 통해 구한 값을 원래 힙에 다시 append 시켜주면 된다. 

 

IndexError 

heapq.heappop(heap)은 더이상 pop할 값이 없는, 즉 빈 힙에서 pop을 할 경우 IndexError를 발생한다. 

만약 더 이상 작은 두 개의 값이 존재하지 않아서 기준에 맞는 새로운 큰 값을 만들 수 없는 경우 -1을 반환해야 하기 때문에 indexError가 일어난 경우 try{} exception{}을 통해서 -1을 반환하도록 해주면 된다.

import heapq

def solution(scovile, k):
    answer = 0
    h = []
    
    for i in scovile:
        heapq.heappush(h, i)
    # it is like that...
    # heapq.heapify(scovile)
    try :
        min_val = heapq.heappop(h)
        while min_val < k: 

            min_val = heapq.heappushpop(h, min_val + heapq.heappop(h) * 2)
            answer += 1

        return answer
        
    except IndexError :
        
        return -1
        
scovile = [1, 2, 3, 9, 10, 12]
k = 7

theAnswer = solution(scovile, k)
print(theAnswer)