[프로그래머스/파이썬] 디펜스 게임

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

프로그래머스

문제 요약 : 준호는 디펜스 게임을 진행한다. 병사는 n명 가지고 있고, 적을 마주할 때 마다 적의 수만큼 아군의 수도 줄어든다. 단, '무적권'이라는 스킬을 사용할 시  병사의 소모없이 한 라운드의 공격을 막을 수 있다. 무적권을 적절히 사용하여 준호가 몇 라운드까지 버틸 수 있는지 출력하라.

 

 

level 2문제길래 가볍게 접근했다가 애를 먹었다.

이진 탐색 + 파라메트릭 서치 + 힙 문제는 사실 초면에 가까웠음 😅

역시 개념으로 아는 것과 직접 풀어보는 것에는 큰 차이가 있다. 꽤나 의미 있는 문제였다.

검색하다보니 백준에도 비슷한 문제가 있길래, 정리하는대로 풀어볼 예정이다.

 

 

맞은 풀이만 궁금하면 시도는 생략하고 풀이부터 봐도 무방합니다.

---

시도 0 ) - 실패

 

그냥 일단 풀어보자! 하고 enemy에서 1. 가장 큰값 2. 인덱스가 작은 값 순으로 찾아내어 0으로 바꾼 후 게임을 진행했다. (그 값들에 무적권을 쓴다고 생각함)

생각해보니 enemy의 값이 엄청 클 경우 그 라운드까지 가지 못하면 아무 소용없는걸 느꼈다.

 

무엇을 기준으로 무적권을 써야하지? 큰 값인건 알겠는데 게임 한 라운드 한라운드 진행될때마다 다르지않나? 라고 생각했다. 결국 생각해보면 그 생각이 힌트였음

 

프로그래머스에 누가 힌트를 적어 두신것을 보고 도움 받았다.

또한 댓글쓰신 분 덕에 파라메트릭 서치를 처음 알게 됐다.

감사합니닷 🥺

검색이나 힌트 없이 풀고 싶었으나.. 

잘 모르는 개념인 것을 알았는데 붙잡고 있는게 더 비효율적이라고 생각했다. 공부를 하고 비슷한 유형 문제를 다시 푸는게 더 도움될 것 같아서 고집을 꺾었다.

 

 

 

시도 1 ) - 실패

무적권으로 모두 막아낼 수 있는 경우는 바로 빠져나가게 하였다.

 

그 외의 경우를 계산하는 것에 초점을 두었다.

일단 한 라운드씩 더 진행할 때마다 answer에 +1을 해줄 것이기 때문에 answer을 k부터 시작하게 하였다.

진행되는 라운드는 game이라는 리스트를 이용했다.

새로운 라운드가 시작될 때마다 적군의 수를 game에 추가하여 sort해주었다.

 

정렬된 game을 기준으로 무적권을 사용하지 않는 라운드의 개수는 i-k개이다. sum을 이용하여 더해주었다.

그 더한 값이 k보다 크게 되면, 게임이 종료되게 작성하였다.

# n 병사 수 , k 무적권 수, enemy 적등장
def solution(n, k, enemy):
    if k >= len(enemy) :    # 무적권으로 모두 막아낼 수 있는 경우
        return len(enemy)
    
    answer = k
    game = enemy[:k]    # k판까지는 무조건 이기기 때문
    for i in range(k,len(enemy)) :
        game.append(enemy[i])
        game.sort()
        if sum(game[:i-k+1]) > n :  # 무적권을 쓰지 않은 라운드의 값들이 n보다 클 때
            break
        else :
            answer += 1
        
    return answer

81점...!

사실 그럴것같았다. 다른분들이 힙을 사용해서 푼 것 같았기 때문이다.

힙과 친하지 않아서 감을 잡고자 list와 sort를 사용한 것이라 이제 힙을 적용해보기로 했다.

 

 

시도 2 ) - 실패 (수정함)

위의 방법을 똑같이 적용했는데 list, pop이 아닌 heappsuh, heappop을 이용했다.

그런데 더 많이 틀린것임.....😨

이때부터 시간을 많이 잡아먹었다.

 

(수정)

사실 이때 풀었던 내 문제가 잘못됐다고 생각했다.

내가 잘못됐다고 생각한건 크게 두가진데

• 최소 값을 이용함
• 누적된 무적권 사용이 아닌 매 라운드마다 새로고침(새로 정렬)

그래서 첫번째 풀이일때 최대 힙을 사용하여 진행했다. (그전의 값을 저장)

 

그런데 풀고보니 최소힙으로도 풀 수 있을 것 같은 그런 느낌이 드는 것이다...

그래서 최소힙으로 풀었는데 풀리는것임

그리고 대체 이 풀이와 시도2의 내 풀이와 뭐가 다른건지 이해가 되지 않았다.

 

고작 몇시간 전이지만

 

사실 왜 heap으로 푼것과 list로 푼 것이 정확도 차이가 나는지는 아직 알지 못하겠음..ㅜㅜ

 

라고 말함 이 이유는 전부 heap에 대한 정확한 이해가 부족했기 때문에 나타났다고 생각한다.

 

결론적으로 말하면 list는 sort를 통해 '정렬'이 되었지만,

heap은 최소 힙, 최대 힙 처럼 최소, 최대값을 보장해줄 뿐이지 '정렬'을 해주지 않는다.

 

결론적으로 나는 list와 똑같이 풀었다고 생각했지만, heap을 사용했기 때문에 다르게 나온 것이다.

 

감사한 블로그

# n 병사 수 , k 무적권 수, enemy 적등장
import heapq

def solution(n, k, enemy):    
    if k >= len(enemy) :    # 무적권으로 모두 막아낼 수 있는 경우
        return len(enemy)
    
    answer = k
    game = enemy[:k]    # k판까지는 무조건 이기기 때문
    heapq.heapify(game)
    
    for i in range(k,len(enemy)) :
        heapq.heappush(game,enemy[i])
        if sum(game[:i-k+1]) > n : 
            break
        answer += 1
        
    return answer

풀이 ) - 최대 힙

최대 힙을 사용하였다.

 

흐름을 정리하면 아래와 같다.

 

1. 무적권의 수가 enemy보다 크거나 같으면 바로 return
2. 아닐 시 ( 무적권을 최대로 사용하여 최대 라운드 수를 계산해야하는 경우 )
   1. 현재 라운드 적의 수를 heap에 넣는다.(최대 힙을 위해 (-) 값으로 넣어줌)
   2. 만일 현재 아군의 수로 게임이 가능하면 공격을 받는다.
      1. 아군의 수에 현재 라운드 적의 수를 빼준다.
      2. answer(진행한 라운드 수)에 +1 해준다.
   3. 만일 현재 아군의 수로 게임이 불가능하고 무적권 횟수가 남아있다면, 무적권을 사용한다.
      1. n값에 현재 적의 수를 빼주고, 가장 큰 적의 수 값을 더해준다.(가장 큰 적의 수에 무적권을 이용하기 위함)
      2. 무적권 횟수를 -1 해준다.
      3. answer에 +1 해준다.
   4. 만일 현재 아군의 수로 게임이 불가능하고 무적권도 없다면 게임을 종료한다.
   5. answer을 return 한다.

# n 병사 수 , k 무적권 수, enemy 적등장
import heapq

def solution(n, k, enemy):        
    if k >= len(enemy) :
        return len(enemy)
    
    answer = 0
    game = []
    
    for i in range(len(enemy)) :
        heapq.heappush(game,-enemy[i])
        if n >= enemy[i] :
            n -= enemy[i]   # 싸움
            answer += 1
        else :
            if k > 0:   # 무적권 사용
                n += -enemy[i] -heapq.heappop(game)
                k -= 1
                answer += 1
            else :  # 무적권 사용할 수 X -> 종료
                break        
    return answer

풀이 ) - 최소 힙

처음엔 최소 값을 계산한것이 잘못됐다고 생각했는데,

생각해보니 최대힙 말고 무적권을 무조건 사용한다(ㅋㅋ)는 가정하에 가장 작은 수를 빼주는 최소힙으로도 풀 수 있을 것 같았다.

바로 적용

참고로 최소힙을 풀면서 내 풀이와 힙에 대해 여러가지를 깨달았는데, 그건 시도2에 자세히 적어뒀음

 

흐름은 아래와 같다.

1. 무적권의 수가 enemy보다 크거나 같으면 바로 return
2. 아닐 시 ( 무적권을 최대로 사용하여 최대 라운드 수를 계산해야하는 경우 )
   1. 무적권의 개수가 남아있으면 무조건 사용한다.
      1. 무적권의 개수를 빼준다.
      2. answer +1 해준다.
      3. heap에 현재 적의 수를 넣어준다.(무적권을 사용한 숫자)
   2. 무적권을 다 썼을 경우
      1. heap에 현재 적의 수를 넣어준다.
      2. heap에서 가장 작은 수를 n에 빼준다.(무적권을 사용하지 않고 그냥 싸울 경우)
      3. 만일 n이 0보다 작으면 진행할 수 없기 때문에 break해준다.
      4. 0보다 크면 answer에  +1 해준다.
3. answer을 return한다.

# n 병사 수 , k 무적권 수, enemy 적등장
import heapq

def solution(n, k, enemy):        
    if k >= len(enemy) :
        return len(enemy)
    
    answer = 0
    use = []
    
    for i in range(len(enemy)) :
        if k > 0 : # 무적권 남아있으면 무조건 사용
            k -= 1
            answer += 1
            heapq.heappush(use,enemy[i])
        else : # 무적권 없을때
            heapq.heappush(use,enemy[i]) # 현재값 넣고
            n -= heapq.heappop(use) # 무적권 안쓸 값
            if n < 0 :
                break
            else :
                answer += 1
            
    return answer