[홀로 하는 코딩 공부] 디펜스 게임(Python)

프로그래머스

사용 언어: Python

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

프로그래머스

 

*** 본 문제를 푸는 과정을 공유하려 한다.

---

▶ 아래 코드처럼 배열을 사용하게 되면 시간초과가 뜬다. 왜냐하면 enemy 배열 길이의 최대가 1,000,000이며 이렇게 긴 배열 내에서 max함수를 사용하여 최대값을 찾게되면 시간소요가 많이 된다.

def solution(n, k, enemy):
    answer = 0
    heap = []
    sum_enemy = 0

    for en in enemy:
        heap.append(en)
        sum_enemy += en
        if sum_enemy > n:
            if k == 0:
                break
            max_value = max(heap)
            sum_enemy -= max_value
            heap.remove(max_value)
            k -= 1
        answer += 1

    return answer

 

 

▶ 배열의 시간초과를 보완해줄 수 있는 것이 heappq이다.heappq를 이용하여 배열에 값을 넣게 되면 넣게 됨가 동시에 자동으로 최소값만을 맨 앞으로 위치시켜준다. 그러므로 해당 문제처럼 최대값 or 최소값만을 찾아야하는 경우 유용하다.

import heapq

def solution(n, k, enemy):
    answer = 0
    heap = []
    sum_enemy = 0

    for en in enemy:
        heapq.heappush(heap, -en)
        sum_enemy += en
        if sum_enemy > n:
            if k == 0:
                break
            sum_enemy += heapq.heappop(heap)
            k -= 1
        answer += 1

    return answer

 

 

▶ heapq를 자주 사용하지않다보니 잊어먹을뻔했다! 잊지말자!!

---

>> 위 내용은 필자가 코딩테스트 문제를 푼 코드입니다.

>> 부족한 점이 많을 수 있기에 잘못된 내용이나 궁금한 사항이 있으면 댓글 달아주시기 바랍니다.

>> 긴 글 읽어주셔서 감사합니다.