[Programmers] 디펜스 게임 - JavaScript

Joosi_Cool·2023년 5월 6일

2단계 JavaScript programmers 디펜스 게임 우선 순위 큐

Programmers

목록 보기

80/98

문제설명

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.

준호는 처음에 병사 n명을 가지고 있습니다.
매 라운드마다 enemy[i]마리의 적이 등장합니다.
남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
- 예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
- 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
무적권은 최대 k번 사용할 수 있습니다.

준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한사항

1 ≤ n ≤ 1,000,000,000
1 ≤ k ≤ 500,000
1 ≤ enemy의 길이 ≤ 1,000,000
1 ≤ enemy[i] ≤ 1,000,000
enemy[i]에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.
모든 라운드를 막을 수 있는 경우에는 enemy[i]의 길이를 return 해주세요.

입출력 예

n	k	enemy	result
7	3	[4, 2, 4, 5, 3, 3, 1]	5
2	4	[3, 3, 3, 3]	4

입출력 예 설명

입출력 예#1

1, 3, 5 라운드의 공격을 무적권으로 막아내고, 2, 4 라운드에 각각 병사를 2명, 5명 소모하면 5라운드까지 공격을 막을 수 있습니다. 또, 1, 3, 4번째 공격을 무적권으로 막아내고, 2, 5 번째 공격에 각각 병사를 2명, 3명 소모하여 5라운드까지 공격을 막을 수 있습니다. 그보다 많은 라운드를 막는 방법은 없으므로 5를 return 합니다.

입출력 예#2

준호는 모든 공격에 무적권을 사용하여 4라운드까지 막을 수 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

설계 과정

이 문제에 핵심은 우선 순위 큐를 사용해야 한다.

우선 우선 순위 큐를 사용하기 위해 관련 클래스를 정의한다.

큐를 만들어두고 capacity 변수를 정의한다. -> 이 변수는 무적권을 쓰지 않고 얼마나 처리했는지에 대한 합이다.

처음 0~k까지 잘라서 그 값을 우선 순위 큐에 넣어둔다.
-> k까지는 무적권을 쓰면 고려대상에서 제외

k부터 enemy끝까지 배열을 아래과정을 돈다.
1) enemy값을 우선 순위 큐에 넣고 제일 큰 값을 pop한다.
2) pop한 값과 capacity를 더해서 n을 넘으면 여기서 stop
-> enemy몇번째까지 했는지 리턴
3) 안넘는다면 그 값은 capacity에 더해준다. -> 무적권을 쓰지 않고 처리한 값

만약 한 바퀴 돌았는데 리턴되지 않았으면 모든 enemy를 돌고도 n을 넘지 않은 것이기 때문에 enemy 개수 전체 리턴

정답 코드

class PriorityQueue {
  constructor() {
      this.heap = [];
  }
  
  push(value) {
      const heap = this.heap;
      heap.push(value);
      let index = heap.length - 1;
      let parent = Math.floor((index - 1) / 2);
      
      while (index > 0 && heap[index] < heap[parent]) {
          [heap[index], heap[parent]] = [heap[parent], heap[index]];
          index = parent;
          parent = Math.floor((index - 1) / 2);
      }
  }
  
  pop() {
      const heap = this.heap;
      if (heap.length <= 1) {
          return heap.pop();
      }
      
      const output = heap[0];
      heap[0] = heap.pop();
      let index = 0;
      
      while (index * 2 + 1 < heap.length) {
          let left = index * 2 + 1, right = index * 2 + 2, next = index;
          
          if (heap[next] > heap[left]) {
              next = left;
          }
          
          if (right < heap.length && heap[next] > heap[right]) {
              next = right;
          }
          
          if (next === index) {
              break;
          }
          
          [heap[index], heap[next]] = [heap[next], heap[index]];
          index = next;
      }
      
      return output;
  }
}

function solution(n, k, enemy) {
  
  let arr = new PriorityQueue();
  var capacity = 0;
 

  //k번째까지는 일단 무적권 쓰면 capacity의 고려 대상에서 제외
  enemy.slice(0,k).forEach((element)=>arr.push(element));
  for(var i  =k;i<enemy.length;i++){
    arr.push(enemy[i]);
    var popNum = arr.pop();
    if(popNum+capacity>n){
      return i;
    }
    capacity+=popNum;
  }

  return enemy.length;
}