99클럽 코테 스터디 9일차 TIL (더 맵게)

 

오늘의 학습 키워드:  힙

문제: 더 맵게

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

프로그래머스

풀이

종료조건만 다르게 생각해서 두 방식으로 풀이했다.

구현 자체는 간단하나 시간 복잡도를 생각해야 하고, 이를 위해 heap 구조를 채용했다.

왜 Heap을 채용해야하는지 heap이 무엇인지 간단하게 알아보겠다.
Heap은 특정한 규칙을 만족하는 이진트리 자료구조이다. (특정 규칙: 최대, 최소)
특징: 완전 이진트리, 삽입&삭제 시 O(log N)의 시간복잡도 -> 배열이나 연결 리스트에 비해 매우 효율적이다.

 

1. 예외처리 방식

heappop이 실패하는 경우에 인덱스 에러를 반환합니다.

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while scoville[0] < K:
        try:
            answer += 1
            made = heapq.heappop(scoville) + heapq.heappop(scoville) * 2
            heapq.heappush(scoville, made)
        except IndexError:
            return -1  
    return answer

 

2. 명시적 조건 검사 & 무한 루프 방지

scoville의 길이가 짧은 경우 (1개 이하) 계산이 안 되는 경우를 탐지 & 값이 더 이상 변하지 않는 경우를 탐지하여 조건을 검사했습니다.

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while scoville[0] < K:
        if len(scoville) < 2:
            return -1
        answer += 1
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)
        made = first + second * 2
        if made == first and made == second:
            return -1
        heapq.heappush(scoville, made)
    
    return answer

 

 

회고

오늘은 이외에도 독서 정리 및 SQL 정리를 진행했습니다.

프로그래머스에서 SQL문제를 실은 다 풀어서 이제는 정리 위주로 진행하며 복습할 계획입니다.

내일 학습할 것.

SQL, Python, 독서