[프로그래머스] Level2 - 디펜스 게임(Javascript)

프로그래머스

📝문제 요약

1️⃣ 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임이다. 

2️⃣ 매 라운드마다 enemy[i]마리의 적이 등장한다. 남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i] 마리의 적을 막을 수 있다.

3️⃣ 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있다. 최대 k번까지 사용가능하다.

4️⃣ 준호가 몇 라운드까지 막을 수 있는지 return하도록 해라.

 

📚중요 포인트

1️⃣ 핵심은 병사의 수가 많이 존재하는 라운드는 최대한 무적권을 사용하면서 병사의 수가 적은 라운드는 준호가 가진 병사로 상대하는 것이다.

2️⃣ 예제를 보면 모든 라운드에 무적권을 사용할 수 있는 경우도 존재한다. 이럴 때는 배열의 길이를 return해 줘야 한다. 

 

❌ 실패 코드(1차 코드)

 function solution(n, k, enemy) {
    let answer = 0;
    // 무적권 사용할 기준점(시작 라운드)
    let standard = enemy[0];
    
    for (let i = 0; i < enemy.length; i++) {
        // 만약 기준점 보다 큰 적의 숫자가 있다면
        if (standard <= enemy[i] && k > 0) {
            // 기준점을 바꾼다. 
            standard = enemy[i];
            // 무적권을 사용
            k--;
            // 라운드 증가
            answer++;
            // 만약 기준점이 더 크다면 
        } else if (n > enemy[i] && standard > enemy[i]){
            // 병사의 수 - 적의 수
            n -= enemy[i];
            // 라운드 증가
            answer++;
        } else {
            break;
        }
    }
    // 모든 라운드를 막을 수 있는 경우에는 enemy[i]의 길이를 return 한다. 
    if (answer === enemy.length) {
        return enemy.length;
    } 
    return answer;
    
 }

 

❗️실패 원인

일단 나의 초기 코드는 너무 1차원적으로 접근해서 풀었다. 효율성이나 풀이 자체가 잘못 되었다. 

그리고 나서, 이 문제는 이분 탐색 && 우선순위 큐를 이용해서 풀어야 한다는 것을 깨달았다. 

 

 

✅ 성공 코드(2차 코드) - 이분 탐색

function solution(n, k, enemy) {
    // 좌측, 우측 지점 초기 설정
    let [left, right] = [0, enemy.length];
    // 중간 지점 설정
    let mid = Math.floor((left + right)/2);
    
    // 우측지점이 좌측지점보다 클 때까지 계속 순회한다.
    while (left <= right) {
        // 무적권 소진을 위해서 중간값까지 slice 후에 적의 숫자가 많은 것부터 무적권 사용을 위해 내림차순을 정렬한다.
        const curSlice = enemy.slice(0, mid).sort((a, b) => b - a);
        // 무적권 횟수
        let noDie = k;
        
        // 무적권 사용 후에 남은 적의 수를 합산해주는 작업을 진행한다.
        const curEnemy = curSlice.reduce((acc, cur) => {
            // 무적권이 존재하면
            if (noDie > 0) {
               // 사용후
               noDie--;
               // 현재 누적값을 return
               return acc;
            }
            // 무적권 사용이 없으면 적의 숫자를 계속 누적
            return acc + cur;
        }, 0)
        
        // 현재 병사의 수가 적의 숫자보다 많으면
        if (n - curEnemy >= 0) {
           // 좌측 지점을 이동해주고
           left = mid + 1;
        // 병사의 수가 적의 숫자보다 적으면
        } else {
           // 우측 지점을 이동해준다.
           right = mid - 1;
        }
        // 중간값을 새로 계산한다.
        mid = Math.floor((left + right) / 2);
    }
    // 최종적으로 좌측지점을 return해준다.
    return left - 1;
    
}

 

이분탐색으로 해결한 문제는 정답이 된다. 하지만 아래와 같이 정확성 테스트를 통과하는데 시간이 많이 걸린다.

정확성 테스트

 

고민 끝에 다른 방법으로 도전해 봤다. 바로 우선순위 큐다. 내 생각에는 이 문제에 가장 잘 맞는 알고리즘이라고 판단했다. 

이 문제의 핵심은 바로 적의 숫자가 많은 라운드에서 무적권을 사용해 주고 적의 숫자가 적은 경우에는 현재 가진 병사의 수로 계산을 해서 최종 라운드를 계산해야 한다.

그래서 우선순위 큐를 구현해 놓으면 훨씬 효율적이겠다는 생각이 들었다. 

 

✅ 성공 코드(3차 코드) - 우선순위 큐

// 우선순위 큐 클래스(최소힙)
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;
        // 힙의 길이가 1이하이면 pop을 해주고 return 한다.
        if (heap.length <= 1) {
            return heap.pop();
        }
        // 부모 노드를 변수에 할당해준다.
        const output = heap[0];
        // 힙의 루트 노드를 힙의 가장 마지막 노드로 대체한다.
        heap[0] = heap.pop();
        // 인덱스의 시작값은 0이다.
        let index = 0;
        
        // 왼쪽 자식 노드가 존재한다면 다음 로직을 실행한다.
        while (index * 2 + 1 < heap.length) {
            // 최소 힙 속성을 유지하기 위해 next변수를 사용(초깃값은 인덱스)
            let left = index * 2 + 1, right = index * 2 + 2, next = index;
            
            // 만약 next에 해당하는 요소가 왼쪽 자식 노드의 요소 보다 크다면
            if (heap[next] > heap[left]) {
                // 왼쪽 자식 노드의 인덱스를 next에 업데이트한다.
                next = left;
            }
            // 만약 오른쪽 자식 노드가 존재하고 next에 해당하는 요소가 오른쪽 자식 노드의 요소 보다 크다면
            if (right < heap.length && heap[next] > heap[right]) {
                // 오른쪽 자식 노드의 인덱스를 next에 업데이트한다.
                next = right;
            }
            // 인덱스랑 next의 값이 같다면 힙이 최소힙의 조건을 유지하고 있으며 down-heap 작업이 필요 없기 떄문에
            // 종료한다.
            if (index === next) {
                break;
            }
            // 치환을 통해서 최소힙의 과정을 계속 진행한다.
            [heap[next], heap[index]] = [heap[index], heap[next]];
            // index를 next로 바꾼다.
            index = next;
        }
        // 힙에 있던 가장 작은 요소를 return한다.
        return output;
    }
}

function solution(n, k, enemy) {
    // 새로운 인스턴스를 생성한다.
    let arr = new PriorityQueue();
    // 적의 숫자를 누적시키기 위한 변수
    let capacity = 0;
    
    // k번째까지는 일단 무적권을 쓰면 capacity의 고려 대상에서 제외한다.
    enemy.slice(0, k).forEach((el) => arr.push(el));
    
    // 무적권 사용 이후부터 배열을 순회하면서
    for (let i = k; i < enemy.length; i++) {
        // 다음 적의 숫자를 넣고 나서 
        arr.push(enemy[i]);
        // 그중에서 가장 작은 값을 빼준다.
        let nowPop = arr.pop();
        // 현재 빼준 값 + 누적된 적의 숫자가 > 병사의 수보다 크면
        if (nowPop + capacity > n) {
            // 현재 해당 인덱스를 return 한다.
            return i;
        }
        // 병사의 수가 더 많으면 적의 숫자를 누적시킨다. 
        capacity += nowPop;
    }
    // 무적권을 다 쓰거나 or 모든 라운드를 막은 경우에는 배열의 길이를 return한다.
    return enemy.length;

}

 

 

정확성 테스트

📔느낀점

👉 우선순위 큐나 이분 탐색 두 개를 쓰던 정답은 된다. 각자의 기호에 맞게 쓰면 된다. 나는 우선순위 큐가 정확성 테스트에서 시간이 훨씬 단축된 것을 봤기 때문에 우선순위 큐가 더 좋다고 생각했다. 

👉 사실 Python을 사용하면 우선순위 큐 라이브러리가 존재하기 때문에 직접 구현할 필요가 없다. 근데 JavaScript는 직접 구현해야 한다. 하지만 이번에 해보니 직접 구현해 보면서 어떻게 동작하는지 직접 눈으로 볼 수 있기 때문에 오히려 나는 좋은 거 같다.