[프로그래머스/JavaScript] Lv.2 디펜스 게임

 

 

 

프로그래머스

 

 

---

1. 문제 설명

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

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

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

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

제한 사항

 

---

2. 입출력 예

입출력 예

 

 

 

 

 

---

3. 문제 풀이

JavaScript에서는 Heap 자료구조가 없기 때문에 직접 구현해주어야 한다. 알고리즘이 영역이 아니라면, 외부 라이브러리를 통해 사용할 수 있다. 해당 문제는 Heap 자료구조를 사용하여 최소 값을 비교하며 풀어나가야 한다.

 

* Heap 자료구조 개념 및 설명

2022.12.10 - [JavaScript] - [JavaScript] JavaScript로 힙(Heap) 구현하기

 

/* 1) Heap 구현 */
class Heap {
    constructor() {
        this.heap = [null];
    }
    
    size() {
        return this.heap.length - 1;
    }
    
    getMin() {
        return this.heap[1] ? this.heap[1] : null;
    }
    
    swap(a, b) {
        [ this.heap[a], this.heap[b] ] = [ this.heap[b], this.heap[a] ];
    }
    
    push(value) {
        this.heap.push(value);
        let curIdx = this.heap.length - 1;
        let parIdx = (curIdx / 2) >> 0;
        
        while(curIdx > 1 && this.heap[parIdx] > this.heap[curIdx]) {
            this.swap(parIdx, curIdx)
            curIdx = parIdx;
            parIdx = (curIdx / 2) >> 0;
        }
    }
    
    pop() {
        const min = this.heap[0];	
        if(this.heap.length <= 2) this.heap = [ null ];
        else this.heap[1] = this.heap.pop();   
        
        let curIdx = 1;
        let leftIdx = curIdx * 2;
        let rightIdx = curIdx * 2 + 1; 
        
        if(!this.heap[leftIdx]) return min;
        if(!this.heap[rightIdx]) {
            if(this.heap[leftIdx] < this.heap[curIdx]) {
                this.swap(leftIdx, curIdx);
            }
            return min;
        }

        while(this.heap[leftIdx] < this.heap[curIdx] || this.heap[rightIdx] < this.heap[curIdx]) {
            const minIdx = this.heap[leftIdx] > this.heap[rightIdx] ? rightIdx : leftIdx;
            this.swap(minIdx, curIdx);
            curIdx = minIdx;
            leftIdx = curIdx * 2;
            rightIdx = curIdx * 2 + 1;
        }

        return min;
    }
}

function solution(n, k, enemy) {
    // 2) Heap 객체를 생성한다.
    let heap = new Heap();
    let answer = 0;
    
    // 3) 공격 횟수 만큼 반복문 생성
    for (let i = 0; i < enemy.length; i++) {
    
       // 4) Heap 안에 무적권(k) 갯수 만큼 담는다.
       if(heap.size() < k) {
           heap.push(enemy[i]);
           answer++;
       } else {
           // 5) Heap의 최솟 값을 찾는다.
           let min = heap.getMin();
           
           // 6) Heap의 최솟 값이 공격하는 값보다 작을 때
           if(enemy[i] > min) {
               // 7) 보유한 병사(n)수에 최솟 값을 뺀다.
               n -= min;
               
               // 8) Heap 최솟 값을 공격 값과 교체 
               heap.pop(min);
               heap.push(enemy[i]);
           } else {
               // 9) Heap의 최솟 값보다 크면 해당 공격 값을 보유한 병사(n)수에서 뺀다.
               n -= enemy[i];
           }
           // 10) 보유한 병사(n)수가 0보다 클때만 라운드(answer) 증가
           n >= 0 && answer++;
       }
    }
    return answer;
}