[프로그래머스 Level 2] 디펜스 게임 (Python 파이썬) 풀이 방법

풀고 싶은 문제가 많았는데 한문제를 푸는데 시간이 꽤나 오래 걸린다. 체력적으로 소모는 많지만 뿌듯함은 커지고, 꾸준함이 중요하다는걸 점점 깨닫는다. 인스타그램을 보면 대부분이 해외로 놀러 나가있던데 물론 부럽지만 한편으로는 이 자리를 지키고 있는 내가 대견스럽기도 하며 미래가 기대되기도 한다. 정말 언젠가는 결실을 맺으리 :)

 

 

프로그래머스 <디펜스 게임> 문제 보기

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

프로그래머스

 

 

프로그래머스 <디펜스 게임> 문제 풀이

import heapq

def solution(n, k, enemy):
    answer = 0
    
    heap = []
    size = 0
    
    if k >= len(enemy):
        return len(enemy)
    
    for i in enemy:
        
        if n - i >= 0:
            n -= i
            heapq.heappush(heap, -i)
            size += 1
        else:
            if k == 0:
                return answer
            k -= 1
            if not size == 0:
                value = -heapq.heappop(heap)
                if value < i:
                    heapq.heappush(heap, -value)
                else:
                    heapq.heappush(heap, -i)
                    n += value
                    n -= i
        answer += 1
        
    return answer

heap에 무적권을 사용하지 않고 병사로 물리친 적 enemy[i]를 저장해주었다. n으로 물리칠 수 있는 값일 경우에는 우선 n값을 빼주었다가, enemy에서 heap의 가장 큰 값보다 더 작은 값이 나왔을 경우 n값과 heap을 변경해주었다. 무적권을 사용해야하는데 무적권이 없을 경우, 더 이상 싸울 수 없다는 뜻이다.

 

 

 

첫 번째 도전

import heapq

def solution(n, k, enemy):
    answer = 0
    
    heap = []
    heapq.heappush(heap, -enemy[0])
    
    for fightEnemy in enemy:
        
        if k == 0:
            return answer
        
        answer += 1
        
        if n - fightEnemy >= 0:
            n -= fightEnemy
            heapq.heappush(heap, -fightEnemy)
        else:
            k -= 1
            value = -heapq.heappop(heap)
            if fightEnemy < value:
                heapq.heappush(heap, -fightEnemy)
            else:
                heapq.heappush(heap, -value)
    
    return answer

첫 번째 도전에서는 heap에 값이 없을 경우를 제대로 고려해주지 않았다는 오류가 있었다. 처음에 값을 넣고 시작하면 될 것이라 생각했지만 바보같이 for문을 처음 값부터 돌렸다.

 

 

두 번째 도전

import heapq

def solution(n, k, enemy):
    answer = 0
    
    heap = []
    size = 0
    
    for i in enemy:
        if n-i >= 0:
            n -= i
            heapq.heappush(heap, -i)
            size += 1
        else:
            if k == 0:
                return answer
            k -= 1
            if not size == 0:
                value = -heapq.heappop(heap)
                if value > i:
                    heapq.heappush(heap, -i)
                else:
                    heapq.heappush(heap, -value)
        answer += 1        
    return answer

두 번째 도전에서는 size 변수를 도입함으로써 heap이 비었을 경우를 체크해줄 수 있었다. 그러나 value와 i 값을 비교하고 heap을 정리하는 과정에서 n 값을 변경해주지 않는 오류를 범했다.

 

 

세 번째 도전

import heapq

def solution(n, k, enemy):
    answer = 0
    
    heap = []
    size = 0
    
    if k >= len(enemy):
        return len(enemy)
    
    for i in enemy:
        
        if n-i >= 0:
            n -= i
            heapq.heappush(heap, -i)
            size += 1
            
        else:
            
            if k == 0:
                return answer
            
            k -= 1
            
            if size == 0:
                heapq.heappush(heap, -i)
            else:
                value = -heapq.heappop(heap)
                
                if value > i:
                    heapq.heappush(heap, -i)
                    n += value
                    n -= i
                else:
                    heapq.heappush(heap, -value)
        
        answer += 1
        
    return answer

세 번째 도전에서는 황당한 실수를 해버렸다. 코드를 계속 보다 보니 헷갈렸는지 heap이 비어있는 경우에 무적권을 사용한 enemy를 넣어주었다. 머릿속이 꼬여버린 거 같아 코드를 싹 지우고 아이패드에 새로 풀어 제출했더니 정답 결과를 얻을 수 있었다.

 

이분탐색을 이용한 방법도 있다는데 최신 문제라 그런지 다른 풀이를 찾아볼 수는 없었다. 이후 스스로 생각해서 풀어보고 글을 다시 남겨야겠다.

 

 

 

어릴 때는 명절이 다가올수록 설레고 들떴다면 이제는 그리 좋지 않다. 그냥 평소 일상처럼 공부하고 싶은데 루틴이 깨져서 조금 아쉬울 뿐이다. 곧 명절인데 다들 즐거운 설날 되세요 :)