프로그래머스 LEVEL 2(디펜스 게임)

사용 언어 : javascript
해결 날짜 : 2022-12-09
해결 방법 :
- 이분탐색을 통해 문제 해결
  - left와 right의 mid(중앙값)를 구함
  - mid가 k(무적권)보다 작거나 같다면, n을 통해 다음 라운드도 진행할 가능성이 있으므로 오른쪽 탐색
  - mid가 k보다 크다면,
    - mid까지의 enemy를 잘라내어 내림차순 정렬(tempEnemy)
    - index를 k부터 시작해 tempEnemy를 돌며
      - sum에 적의 수를 추가
      - 이 때 sum이 n보다 커지면 mid까지는 막을 수 없는 라운드이므로 왼쪽 탐색,
      - 반복문 종료후에도 sum이 n보다 작거나 같다면 다음 라운드도 진행할 가능성이 있으므로 오른쪽 탐색
회고 :
- 처음에 단순 array를 정의해 매번 정렬 후 max값을 교체해 주는 방식으로 문제를 해결하려고 하였으나 당연하게도 시간 초과
- 그 후 map 자료구조를 사용해 문제를 해결하려 했으나 한 개의 테스트 케이스가 시간 초과
- map 자료구조를 이용하더라도 반복문 안에서 계속 Math.max()를 사용하기 때문에 문제가 발생한 것으로 추측됨
- 그 후 우선순위큐를 직접 구현하여 문제를 해결
- 우선순위큐 말고도 이분 탐색으로도 문제를 해결 가능하다.

이분탐색 코드

function solution(n, k, enemy) {
  let left = 0,
    right = enemy.length;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (mid <= k) {
      left = mid + 1;
      continue;
    }

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

    for (let i = k; i < tempEnemy.length; i++) {
      sum += tempEnemy[i];

      if (sum > n) {
        isLeft = false;
        break;
      }
    }

    if (isLeft) {
      left = mid + 1;
    } else right = mid - 1;
  }

  return left - 1;
}

우선순위 큐 코드

class PriorityQueue {
  constructor(comp) {
    this.heap = [];
    this.comp = (a, b) => {
      return b - a;
    };
  }
  dequeue() {
    if (this.isEmpty()) return null;

    let max = this.max();
    let last = this.heap.pop();

    if (this.size() != 0) {
      this.heap[0] = last;
      this.downHeap(0);
    }

    return max;
  }
  downHeap(pos) {
    while (this.isInternal(pos)) {
      let s = null;

      if (!this.hasRight(pos)) {
        s = this.left(pos);
      } else if (this.comp(this.heap[this.left(pos)], this.heap[this.right(pos)]) <= 0) {
        s = this.left(pos);
      } else {
        s = this.right(pos);
      }
      if (this.comp(this.heap[s], this.heap[pos]) < 0) {
        this.swap(pos, s);
        pos = s;
      } else break;
    }
  }
  upHeap(pos) {
    while (!this.isRoot(pos)) {
      let p = this.parent(pos);
      if (this.comp(this.heap[p], this.heap[pos]) <= 0) break;

      this.swap(p, pos);
      pos = p;
    }
  }
  swap(x, y) {
    let temp = this.heap[x];
    this.heap[x] = this.heap[y];
    this.heap[y] = temp;
  }
  parent(pos) {
    return parseInt((pos - 1) / 2);
  }
  left(pos) {
    return 2 * pos + 1;
  }
  right(pos) {
    return 2 * pos + 2;
  }
  size() {
    return this.heap.length;
  }
  isInternal(pos) {
    return this.hasLeft(pos);
  }
  isRoot(pos) {
    return pos === 0;
  }
  hasLeft(pos) {
    return this.left(pos) < this.size();
  }
  hasRight(pos) {
    return this.right(pos) < this.size();
  }
  isEmpty() {
    return this.heap.length == 0;
  }
  enqueue(value) {
    this.heap.push(value);
    this.upHeap(this.size() - 1);
  }
  max() {
    return this.heap[0];
  }
  min() {
    return this.heap[this.size() - 1];
  }
}

function solution(n, k, enemy) {
  let answer = 0;
  const map = new Map();
  const priorityQ = new PriorityQueue();

  for (const e of enemy) {
    if (n < e && k === 0) break;

    if (n >= e) {
      n -= e;
      answer += 1;
      priorityQ.enqueue(e);
      continue;
    }

    const max = priorityQ.max();

    if (max > e) {
      n = n + max - e;
      priorityQ.dequeue(e);
      priorityQ.enqueue(e);
      map.has(e) ? map.set(e, map.get(e) + 1) : map.set(e, 1);
    }

    k -= 1;
    answer += 1;
  }

  return answer;
}

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