[1스4코1파] #104. LV 2. 디펜스 게임

gunny·2023년 4월 17일

1스4코1파 heapq 코딩테스트 코딩테스트 heapq 문제 코딩테스트 python 프로그래머스 heapq 프로그래머스 디펜스 게임 프로그래머스 디펜스 게임 python

코딩테스트

목록 보기

104/530

[1스4코1파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 1명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (104일차)
[4코1파] 2023.01.13~ (95일차)
[1스4코1파] 2023.04.12~ (6일차)

Today :

2023.04.17 [104일차]

프로그래머스 LV 2
디펜스 게임
https://school.programmers.co.kr/learn/courses/30/lessons/142085

문제 설명

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.

준호는 처음에 병사 n명을 가지고 있습니다.
매 라운드마다 enemy[i]마리의 적이 등장합니다.
남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
무적권은 최대 k번 사용할 수 있습니다.
준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한사항

1 ≤ n ≤ 1,000,000,000
1 ≤ k ≤ 500,000
1 ≤ enemy의 길이 ≤ 1,000,000
1 ≤ enemy[i] ≤ 1,000,000
enemy[i]에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.
모든 라운드를 막을 수 있는 경우에는 enemy[i]의 길이를 return 해주세요.

입출력 예

입출력 예 설명

입출력 예#1

1, 3, 5 라운드의 공격을 무적권으로 막아내고, 2, 4 라운드에 각각 병사를 2명, 5명 소모하면 5라운드까지 공격을 막을 수 있습니다. 또, 1, 3, 4번째 공격을 무적권으로 막아내고, 2, 5 번째 공격에 각각 병사를 2명, 3명 소모하여 5라운드까지 공격을 막을 수 있습니다. 그보다 많은 라운드를 막는 방법은 없으므로 5를 return 합니다.
입출력 예#2

준호는 모든 공격에 무적권을 사용하여 4라운드까지 막을 수 있습니다.

문제 풀이 방법

이 문제로 말할 것 같으면 우선순위 큐를 이용한
파이썬에서 최소힙 heapq 을 import 해서 풀면 되는 문제다
호호

뭘 호호야.. 실패인데

왜 틀렸는지 낸들 알 수 없어서 구글링하던 차에
heap 에서 heappushpop 이라는게 있다는 걸 알게 됨

내 코드

import heapq

def solution(n, k, enemy):
    heap = enemy[:k]
    heapq.heapify(heap)
    
    for i in range(k, len(enemy)):
        n -= heapq.heappushpop(heap, enemy[i])
        
        if n<0:
            return i

    return  len(enemy)

증빙