[프로그래머스] 디펜스 게임 JAVA

AMUD·2022년 12월 9일
0

Algorithm

목록 보기
53/78

문제

문제링크

접근

  • enemy의 길이가 짧지만은 않아서 모든 경우의 수를 따지기에는 부담이 따를 것이라고 예상했다.
  • 사고의 흐름은 지금까지의 뺀 값들 중에 가장 큰 것을 롤백한다는 상상이 먼저 떠올랐다.
  • 그래서 거쳐온 모든 값을 저장해놓고, 그 중에 최대값을 다시 복구하는 순서로 구현하였다.
  • 최대값을 얻는 방법은 저장할 때부터 우선순위큐에 넣는 방법으로 구현하였다.

소스코드

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = enemy.length;
        Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        int my = n;
        int card = k;
        for (int i = 0; i < enemy.length; i++) {
            my -= enemy[i];
            pq.add(enemy[i]);

            if (my < 0) {
                if (card > 0 && !pq.isEmpty()) {
                    my += pq.poll();
                    card--;
                } else {
                    answer = i;
                    break;
                }
            }
        }

        return answer;
    }
}
profile
210's Velog :: Ambition Makes Us Diligent

1개의 댓글

comment-user-thumbnail
2024년 3월 13일

감사합니다! 핵심아이디어를 롤백으로 설명해주셔서 바로 이해되네요!

답글 달기