더 맵게

문제풀이

효율성 실패

이번 코딩 문제는 힙을 이용해야 하는 문제인데 내가 처음 문제를 풀었던 코드는 한 번 과정을 거칠 때마다 sort()를 이용해 정렬을 하였다. 결국 이것이  비효율적인 시간을 지출해 문제를 통과하지 못했다.

효율성 해결

import heapq

def solution(scoville, K):
    answer = 0
    
    scoville.sort()
    if scoville[0] == 0 and scoville[1] == 0:
        return -1
        
    heapq.heapify(scoville) 
    
    while(scoville[0] < K and len(scoville) > 1):
        x = heapq.heappop(scoville)
        y = heapq.heappop(scoville)
        new_scoville = min(x, y) + max(x, y) * 2
        
        heapq.heappush(scoville, new_scoville)
        
        answer += 1
    
    if scoville[0] < K:
        answer = -1
    
    return answer

heapq를 import 하여 따로 heap을 생성하는 함수를 만들지는 않았다. heap에 관한 자세한 내용은 아래에 첨부한다.

알고리즘

Heap

부모의 값이 자식의 값보다 항상 크다(자식의 값 <= 부모의 값)라는 조건을 만족하는 완전 이진트리이다. (반대의 경우도 힙이라고 한다.)

또 형제의 대소 관계가 정해져 있지 않으므로 부분 순서 트리(partial ordered tree)라고도 한다.

 

힙을 배열에 저장하면 부모 인덱스, 왼쪽 자식, 오른쪽 자식은 다음과 같은 관계가 성립한다.

원소 a[i]에서

• 부모: a[(i-1) // 2]
• 왼쪽 자식: a[i * 2 +1]
• 오른쪽 자식: a[i * 2 + 2]

힙은 일반적으로, 리스트에서 가장 작은(또는 가장 큰) 요소에 반복적으로 접근하는 프로그램에 유용하다.

힙을 사용하면 가장 작은(또는 가장 큰) 요소를 처리하는 시간 복잡도는 O(n)이고, 그 외의 조회, 추가, 수정을 처리하는 시간 복잡도는 O(log n)이다.                               

Heap 정렬의 특징

힙에서 최댓값은 루트에 위치한다는 특징을 이용한다. 구체적으로 다음의 과정을 반복한다.

1. 힙의 최댓값인 루트를 꺼낸다.
2. 마지막 원소(가장 하단의 오른쪽에 위치한 원소)를 루트로 이동한다.
3. 루트에서 시작하여 자신보다 값이 큰 자식과 자릴 바꾸고 아래쪽으로 내려가는 작업을 반복한다. 자식의 값이 작거나 리프의 위치에 도달하면 종료한다.

출처

문제: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

코딩테스트 연습

파이썬 자료구조와 알고리즘 - 미아 스타인 저/최길우 역

Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편 - 시바타 보요 저/강민 역