디펜스 게임 js 프로그래머스

문제 요약

내 병사 수 와 패스권 적의 수(배열)이 주어진다. 내 병사수로 최대한 막을 수 있는 라운드를 리턴하면 되는 문제이다.

• 예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
• 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.

내가 푼 풀이

엄청 오래 시도했던 문제다. 처음 도전하고 실패하고 몇달뒤에 도전하고 실패하고 몇달뒤에 도전 하고 이런 식이었나 보다.

첫 시도

처음에는 뭣도 모르고 문제를 푼것 같다. 이전에 풀었던 것을 다 주석처리 해놓고 다시 풀때마다 아래에 새로 풀었는데 기록해놔서 다행이다.
처음에는 que 방법으로 문제를 풀었나 보다 단순히 순차대로 적수를 빼주고 뺄때 마이너스가 되면 패스권 쓰는 이런 방식이었다.
왜 que 를 썻는지 모르겠다. 처음이라 잘 몰라서 썻나

function solution(n, k, enemy) {
    var answer = -Infinity;
    let que = [];
    que.push({'solider':n,'pass':k,'enemy':enemy,'index':0});
    let round = 0;
  while(que.length){

    let {solider,pass,enemy,index} = que.shift();
  
    answer = Math.max(round,answer);
     round=0;
    for(let i =0; i<enemy.length;i++){
  
      const phase = enemy[i];
        if(answer>round){
            break;
        }
      if(solider<1){
        round--
        break;
      }
    
      if((solider<phase && pass) || (i==index&&pass)){
        pass--
        round++
      }else{
        solider-=phase
        round++
      }
    }
     if(index!=enemy.length-1){
      que.push({'solider':n,'pass':k,'enemy':enemy,'index':index+1})
    }
  
  }
    return answer;
}

두번째 시도

이것도 순차대로 빼주고 라운드별로 가장 큰 값을 패스권 쓸때 빼서 더해준다.
shift를 써서 시간이 오래걸리긴 했을 것이다.

function solution(n, k, enemy) {
    let round = 0;
    let passArr = [];
    while(enemy.length){
      let phase = enemy.shift();
        n-=phase;
        passArr.push(phase);
      
       if(n<1 && !k){
        break;
      }
     
      if(n<1 && k){
        let max = Math.max(...passArr);
        n+=max;
        k--
      }
      // console.log(phase,n,k)
      round++
    }

    return round;
} 

세번째 시도

세번째는 그래도 주석으로 남겨놨던 모양이다. 투포인트(?) 윈도우(?) 기법으로 문제를 풀었나보다.
나름 체계적이라서 한번 돌려보니
// 5 10 11 13 14 16 17 18 19 22 28 이를 통과하지 못했다

// function solution(n, k, enemy) {
//   let left = 1; // 최소 라운드 수
//   let right = enemy.length; // 최대 라운드 수
//   let answer = 0;
  
//   while (left <= right) {
//     let mid = Math.floor((left + right) / 2); // 중간값
//     let soldiers = n; // 현재 남은 병사 수
//     let invincible = k; // 현재 남은 무적권 사용 가능 횟수
//     let possible = true; // mid 라운드까지 모든 적을 막을 수 있는지 여부
    
//     for (let i = 0; i < mid; i++) {
//       // 현재 라운드에서 필요한 병사 수
//       let required = enemy[i] - soldiers;
      
//       // 무적권 사용 가능하면 사용
//       if (required > 0 && invincible > 0) {
//         invincible--;
//       }
//       // 무적권 사용 불가능하면 라운드 종료
//       else if (required > 0 && invincible === 0) {
//         possible = false;
//         break;
//       }
      
//       soldiers -= Math.min(soldiers, enemy[i]);
//     }
    
//     // mid 라운드까지 모든 적을 막을 수 있으면 답 갱신하고, 라운드 수를 늘려서 탐색 계속 진행
//     if (possible) {
//       answer = mid;
//       left = mid + 1;
//     }
//     // mid 라운드까지 모든 적을 막을 수 없으면 라운드 수를 줄여서 탐색 계속 진행
//     else {
//       right = mid - 1;
//     }
//   }
  
//   return answer;
// }

네번째 시도

이것도 단순하게 적수를 빼가면서 패스권을 사용해 가는 문제로 풀었다

function solution(n, k, enemy) {
  var answer = 0;
  let pass = k;
  let life = n;
  let bigNum = Math.floor(n / 2);
  let bigRound = [];
  for (let i = 0; i < enemy.length; i++) {
    let round = i + 1;
    let enemys = enemy[i];
    if (life - enemys <= 0) {
      if (pass > 0) {
        if (enemys >= bigNum) {
          pass--;
          bigNum = enemys;
          bigRound.push(i);
          answer = round;
          continue;
        } else {
          pass--;
          let bonus = bigRound.pop();

          life += enemy[bonus];
        }
      } else {
 
        return round - 1;
      }
    }
    life = life - enemys;
          if (enemys >= bigNum) {
      bigNum = enemys;
      bigRound.push(i);
    }
    answer = round;
  }

  return answer;
}

단순하게 순서대로 진행하면서 적수를 빼주고 패스권일때는 큰수를 더해주는 방법을 사용했었다.

거의 마지막 도전때서야 이문제가 최대힙을 구해야 한다는 것을 깨닫게 되었다.
문제를 다시 읽어도 이게 왜 최대힙인지 바로 이해가 가지 않는다. 아직 많이 부족한듯 싶다

최대힙을 적용해서 문제를 풀게 되었다.
나는 최소힙에 음수를 넣으면 최대힙이라고 해서 최소힙으로 구했다.

마지막 도전

function solution(n, k, enemy) {
  var answer = 0;
  let heap = new MinHeap();
  let pass = k;
  let life = n;
  for (let e of enemy) {
    if (life - e < 0) { // 이곳에서 문제 이곳에 처음이 life-e <=0  이었다. 
      if (pass > 0) {
        --pass;
           let heapMax = Math.abs(heap.poll());
        let plus;
        if (heapMax > e) {
          plus = heapMax;
          life += plus;
        } else {
          heap.add(-heapMax);
          answer++;
          continue;
        }
      } else {
        if (life - e === 0) {
          answer++;
        }
    
        break;
      }
    }
    heap.add(-e);
 
    life = life - e;

    answer++;
  }

  return answer;
}
class MinHeap {
  constructor() {
    this.heap = [];
  }
  size() {
    return this.heap.length;
  }
  swap(idx1, idx2) {
    [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
  }
  add(value) {
    this.heap.push(value);
    this.bubbleUp();
  }
  poll() {
    if (this.size() < 2) {
      return this.heap.pop();
    }
    let min = this.heap[0];
    let last = this.heap.pop();
    this.heap[0] = last;
    this.bubbleDown();
    return min;
  }
  bubbleUp() {
    let index = this.size() - 1;
    let parrentIdx = Math.floor((index - 1) / 2);
    while (parrentIdx >= 0 && this.heap[parrentIdx] > this.heap[index]) {
      this.swap(parrentIdx, index);
      index = parrentIdx;
      parrentIdx = Math.floor((index - 1) / 2);
    }
  }
  bubbleDown() {
    let index = 0;
    const length = this.heap.length;

    while (true) {
      let leftIdx = index * 2 + 1;
      let rightIdx = index * 2 + 2;
      let smallestIdx = index;

      if (leftIdx < length && this.heap[leftIdx] < this.heap[smallestIdx]) {
        smallestIdx = leftIdx;
      }

      if (rightIdx < length && this.heap[rightIdx] < this.heap[smallestIdx]) {
        smallestIdx = rightIdx;
      }

      if (smallestIdx === index) break;

      this.swap(index, smallestIdx);
      index = smallestIdx;
    }
  }
}

문제를 풀다보니 확실히 패스권은 큰수일때 써야 하는데 큰라운드를 어떻게 알수 있을까 ? 에 대해 고민했던것 같다
객체로 라운드마다 적수를 저장해 놓고 큰 값을 빼야 하나 ? 큰 값인지는 어떻게 알지 ?
이렇게 생각하다보니 큰값은 최대힙으로 해야지 빠르구나 라는 것을 알게 되었다.

처음 문제를 풀때 위에서 작성한대로 life-e <=0 조건을 넣었다.
왜냐하면 내 아군수가 0이 되면 게임이 종료된다고 생각되었기 때문이다.
실제 게임에서도 패스권이 있어도 아군 수가 0이 되면 게임이 종료 되기 때문에 이렇게 당연하게 생각했던것 같다.
그래서 내 아군수가 0이 되지 않게 패스권을 사용하는 조건을 넣었는데 계속 문제에서 통과가 안되는 것이었다

최대 힙 구했고 생각대로 코드를 구현했는데 왜 통과되지않을까 에 대해서 반례를 찾아보니
반례는 아래와 같았다
4, 4, [2, 2, 2, 2, 3, 3]
답은 6라운드 인데 나는 5라운드 가 나왔다.
그래서 어떻게 돌아가나 종이에 넣고 작성해봤는데 작성해봐도 5라운드가 나왔다 반례가 맞는가? 생각하게 되었고
GPT에게 물어봐도 6라운드 란다

내가 생각한 방법이다

첫 라운드 적 2 아군 4 : 가능하니 빼준다 라운드 통과 : 내 아군수 2 패스권 4
2 라운드 적 2 아군 2 : 2-2 는 0이니 불가능하니 패스권을 사용해준다 내 아군수 2 패스권 3
3라운드 적2 여기도 2-2는 0이라서 불가능하니 패스권 사용 : 내아군수 2 패스권 2
4라운드 적 2 여기도 2-2 라서 불가능하니 패스권 사용 : 내 아군수 2 패스권 1
5라운드 적 3 아군 2 여기는 3-2 라서 음수라서 게임 종료
그럼 최대로 도달한 라운드가 5라운드라서 5라고 계속 머리속으로 생각해왔다.
어떻게 해도 6라운드를 가는게 이해가 안되었다

그런데 반대로 아군수가 0이라도 패스권이 남아있으면 다음라운드 진출이 가능하다면 ? 이라는 가설이 떠올랐고
적용해봤다

첫 라운드 적 2 아군 4 : 가능하니 빼준다 아군 2 패스 4
2라운드 적 2 아군 2 일단 가능하다고 생각한다 아군 0 패스 4
3라운드 적 2 패스권 사용 패스 3
4라운드 적 2 패스권 사용 패스 2
5라운드 패스권 사용 패스 1
6라운드 패스권 사용

이러면 6라운드 까지 진행이가능하다
이게 맞는건가 ? 라고 생각해서 조건을 life-e <0 이라고 수정하니
결과는 다통과할수 있었다

조건을 보면 • 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
라고 써있는데 같을 경우는 종료가 안되는것을 인지 못해버렸다

그냥 내 생각대로 이해하고 문제를 풀었는데 문제를 제대로 이해 하는게 필요하다는 것을 깨닫게 되었다.

다른 사람의 풀이

function solution(n, k, enemy) {
    let lt = 0, rt = enemy.length;

    while(lt <= rt) {
        let mid = Math.floor((lt+rt) / 2);
        if(check(n, k, mid, enemy)) lt = mid+1;
        else rt = mid - 1;
    }

    return lt - 1;
}

const check = (n, k, mid, enemy) => {
    if (mid <= k) return true;

    let t = enemy.slice(0, mid).sort((a, b) => b - a);
    let sum = 0;

    for (let i = k; i < t.length; i++) {
        sum += t[i];
        if (sum > n) return false;
    }
    return true;

}

이분 탐색으로 문제를 풀었다 내가 3번째 시도때 이런 이분탐색을 적용한것 같은데 해설을 그때 이분 탐색으로 본 모양이다
다른 분들은 거의 힙 , 이분 탐색 이렇게 푼것같다.