23.02.14 파이썬 코딩 퀴즈#155 디펜스 게임 (프로그래머스 스쿨)

이번 문제는 디펜스 게임 문제이다.

처음 소유한 병사 n 명이며, 매 라운드마다 적들이 등장한다. 다음 라운드로 진출하게 되면 병사는 n-enemi[i] 만큼 감소하게 된며, 최종적으로 남은 병사보다 현재 라운드의 적의 수가 더 많으면 게임이 종료된다.

이때 '무적권' 이라는 스킬이 있으며, 최대 k번 사용 가능하다. 무적권을 사용하면 병사의 소모 없이 한 라운드의 공격을 막을 수 있다.

특별한 예시는 없고, 모든 라운드를 막을 수 있는 경우에는 enemy의 길이를 반환하면 된다.

입출력 예 1을 살펴보면, 2,4라운드에 병사를 2명 5명 소모하여 남은 병사수가 0 이 되었지만, 무적권이 1번 남은 상태이기 때문에 5 라운드로 진출 하였고, 무적권을 사용하여 5 라운드를 해결 하였기 때문에 5를 return 한다.

문제의 핵심은 무적권 k 의 사용 시점에 있다.

내가 생각한 무적권의 사용 시점은

1. 현재 남은 체력이 적들의 수 보다 많은 경우

2. 현 라운드 적의 숫자가 전체 라운드의 평균보다 많은 경우.

1번의 경우는 더 많은 스테이지를 가기 위해서는 당연히 그렇게 써야하는 상황이 되고, 2번의 경우는 무적권 한장으로 적 1명의 라운드를 통과한는 것보단, 적 10명이 있는 라운드를 통과하는게 효율적이기 때문이다.

 

첫번째 작성한 코드이다.

먼저 돌파권이 라운드 수 이상인 경우는 예외처리해 주고 시작하였다.

total_n 은 지금까지 돌파한 스테이지의 수의 적이 합산되어 누적된다.

먼저 현재 체력(n)으로 돌파 가능한 스테이지를 쭉쭉 돌파해 나간다.

더 이상 돌파가 불가능 하고, 돌파권이 있다면 이제 돌파권을 사용할 차례이다.

돌파권은 지금까지 돌파한 스테이지 중에 가장 적 수가 많은 스테이지를 대상으로 한다. 따라서 이미 돌파한 stage 에서 max() 값을 찾아 변수로 선언한뒤 해당 수만큼 total_n에서 삭제 후 stage 에서도 그 값을 제거해 준다.

총 4개의 테케에서 시간 초과가 떴다.

해당 코드를 좀 더 빠르게 실행할 방법을 찾아야 한다.

생각해낸 방법은 heapq 이다. heapq는 기본적으로 가장 최소값을 제일 앞으로 가져와 정렬해주며, 그 뒤로는 이진형태의 정렬 구조를 가진다. 굉장히 특이한 형태이며, 가장 중요한 사신은 heap[0]은 언제나 heap의 가장 작은 값 이라는 점이다.

이를 활용하기 위해 e 값을 음수로 변환하여 전달한다.

heappush(heap, item) 는 말그대로 대상 heap에 heap의 불변성을 유지하며 item 을 집어 넣는다는 뜻이다.

heappushpop(heap, item)은 대상 heap 에 해당 item 을 집어 넣은 뒤 다시 가장 작은 항목을 꺼낸다는 뜻이다. 즉 heappush()와 heappop()이 결합된 형태로, 두 가지를 분리해 사용하는 것보다 더 효율적으로 실행된다.