[Programmers] Level 2. 디펜스 게임

2025. 1. 6. 00:54·코딩테스트/Python
728x90
반응형

🔗 Problem Link

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr


❔Thinking

  • enemy에 담긴 적들을 라운드마다 차례대로 제거할때, 가장 많은 라운드 버틸 방법을 생각한다.
  • '무적권'은 k개 만큼 쓸 수 있고, 쓰는 라운드에 따라 결과가 달라질 수 있다.
  • n=10, k=1일 경우, [10,3,7]을 1라운드만에 끝나거나 3라운드 모두를 버틸 수 있다.

💻Solution

import heapq

def solution(n: int, k: int, enemy: list) -> int:
    max_heap = []  # 지금까지 만난 적을 저장할 최대 힙

    for round_num, e in enumerate(enemy):
        n -= e  # 현재 적을 체력으로 처리
        heapq.heappush(max_heap, -e)  # 최대 힙에 현재 적 추가
        
        if n < 0:  # 체력이 부족한 경우
            if k > 0:  # 무적권을 사용할 수 있으면
                n -= heapq.heappop(max_heap)  # 가장 큰 적을 무적권으로 대체
                k -= 1
            else:  # 무적권도 없으면 종료
                return round_num

    return len(enemy)  # 모든 라운드를 성공적으로 처리

🗝️keypoint

  1. 무적권은 가장 큰 적에게 사용할수록 이득이기 때문에, n이 0이하일때 무적권을 쓸 수 있는 적들을 생각한다.
  2. brute force 방법으로는 더 효율적인 대결을 확인할 수 없다. (ex - [10,3,7])
저작자표시 (새창열림)

'코딩테스트 > Python' 카테고리의 다른 글

[Beakjoon] 4195. 친구 네트워크  (0) 2025.01.08
[Programmers] Level 2. 퍼즐 게임  (0) 2025.01.06
[Beakjoon] 20040. 사이클 게임  (0) 2025.01.03
[Beakjoon] 1213. 펠린드롬 만들기  (0) 2025.01.02
99클럽 코테 스터디 0일차 TIL (floyd-warshall)  (0) 2024.10.28
'코딩테스트/Python' 카테고리의 다른 글
  • [Beakjoon] 4195. 친구 네트워크
  • [Programmers] Level 2. 퍼즐 게임
  • [Beakjoon] 20040. 사이클 게임
  • [Beakjoon] 1213. 펠린드롬 만들기
swwho
swwho
일상을 데이터화하다
  • swwho
    하루한장
    swwho
  • 전체
    오늘
    어제
    • 분류 전체보기 (189) N
      • ML_DL (40) N
        • MUJAKJUNG (무작정 시리즈) (19) N
        • 딥러닝 공부하기 (21)
      • 데이터사이언스 (1)
        • EDA (1)
        • 데이터과학을 위한 통계 (0)
      • 데이터엔지니어링 (2)
      • 논문리뷰 (2)
        • Computer Vision (2)
      • Python 활용하기 (12)
      • 코딩테스트 (127)
        • Python (109)
        • MySQL (14)
      • Git (3)
      • MySQL 활용하기 (0)
      • 일상 이야기 (1)
  • 블로그 메뉴

    • 홈
    • 태그
  • 최근 글

  • 250x250
  • hELLO· Designed By정상우.v4.10.3
swwho
[Programmers] Level 2. 디펜스 게임
상단으로

티스토리툴바