[Algorithm] 숫자 게임

📋 문제

xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다.

• 먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다.
• 각 사원은 딱 한 번씩 경기를 합니다.
• 각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀은 승점을 1점 얻게 됩니다.
• 만약 숫자가 같다면 누구도 승점을 얻지 않습니다.

전체 사원들은 우선 무작위로 자연수를 하나씩 부여받았습니다. 그다음 A팀은 빠르게 출전순서를 정했고 자신들의 출전 순서를 B팀에게 공개해버렸습니다. B팀은 그것을 보고 자신들의 최종 승점을 가장 높이는 방법으로 팀원들의 출전 순서를 정했습니다. 이때의 B팀이 얻는 승점을 구해주세요.
A 팀원들이 부여받은 수가 출전 순서대로 나열되어있는 배열 A와 i번째 원소가 B팀의 i번 팀원이 부여받은 수를 의미하는 배열 B가 주어질 때, B 팀원들이 얻을 수 있는 최대 승점을 return 하도록 solution 함수를 완성해주세요.

 

제한 사항

• A와 B의 길이는 같습니다.
• A와 B의 길이는 1 이상 100,000 이하입니다.
• A와 B의 각 원소는 1 이상 1,000,000,000 이하의 자연수입니다.

 

입출력 예

[5,1,3,7]	[2,2,6,8]	3
[2,2,2,2]	[1,1,1,1]	0

 

✏️ 풀이

모든 상황을 비교하기에는 각 배열의 길이가 크기 때문에 절대 불가능할 것이라고 생각했다. B팀이 많이 이기기 위해서는 A팀이 큰 수일 때 절대 이기지 못하는 경우에 제일 작은 수를 이길 수 있는 경우에 작은 수로 이길 수 있다면 작은 수를 큰 수로 이겨야 한다면 큰수를 내는 것이 큰 수를 아끼며 최선의 방향으로 가는 것이라고 생각했다.

 

A팀의 순서는 상관없이 많이 이기는 경우를 찾는 것이기 때문에 먼저 A팀을 큰수대로 정렬해주고 비교해야 했다. 수가 섞여있는 경우 앞서 세운 전략을 사용할 수 없기 때문이다. 그리고 가장 작은 수와 큰 수를 관리하기 위해서 max heap, min heap을 사용했다. 위에서 세운 전략대로 정렬된 A의 원소와 비교했다.

 

1. 만약 가장 작은 수로 이길 수 있는 경우에는 min heap에서 값을 빼고 이기는 경우이므로 answer를 증가시킨다. 
2. 가장 큰 수로 이길 수 없는 경우 min heap에서 제일 작은 값을 빼고 지는 경우이기 때문에 answer를 증가시키지 않는다.
3. 위의 조건을 통과하고 큰 수로 이길 수 있는 경우에는 max heap에서 값을 빼고 answer를 증가시킨다.

 

⌨️ 코드

class MinHeap {
  constructor() {
    this.heap = [];
    this.heap.push(-1e9);
  }

  insert(value) {
    this.heap.push(value);
    this.upheap(this.heap.length - 1);
  }

  upheap(pos) {
    let temp = this.heap[pos];

    while (temp < this.heap[parseInt(pos / 2)]) {
      this.heap[pos] = this.heap[parseInt(pos / 2)];
      pos = parseInt(pos / 2);
    }
    this.heap[pos] = temp;
  }

  get() {
    if (this.size() === 0) return;
    if (this.size() === 1) return this.heap.pop();
    const result = this.heap[1];
    this.heap[1] = this.heap.pop();
    this.downheap(1, this.heap.length - 1);
    return result;
  }

  show() {
    if (this.size() === 0) return;
    return this.heap[1];
  }

  downheap(pos, len) {
    let temp = this.heap[pos],
      child;
    while (pos <= parseInt(len / 2)) {
      child = pos * 2;
      if (child < len && this.heap[child] > this.heap[child + 1]) child++;
      if (temp <= this.heap[child]) break;
      this.heap[pos] = this.heap[child];
      pos = child;
    }
    this.heap[pos] = temp;
  }

  size() {
    return this.heap.length - 1;
  }
}

class MaxHeap {
  constructor() {
    this.heap = [];
    this.heap.push(1e9);
  }

  insert(value) {
    this.heap.push(value);
    this.upheap(this.heap.length - 1);
  }

  upheap(pos) {
    let temp = this.heap[pos];

    while (temp > this.heap[parseInt(pos / 2)]) {
      this.heap[pos] = this.heap[parseInt(pos / 2)];
      pos = parseInt(pos / 2);
    }
    this.heap[pos] = temp;
  }

  get() {
    if (this.size() === 0) return;
    if (this.size() === 1) return this.heap.pop();
    const result = this.heap[1];
    this.heap[1] = this.heap.pop();
    this.downheap(1, this.heap.length - 1);
    return result;
  }

  show() {
    if (this.size() === 0) return;
    return this.heap[1];
  }

  downheap(pos, len) {
    let temp = this.heap[pos],
      child;
    while (pos <= parseInt(len / 2)) {
      child = pos * 2;
      if (child < len && this.heap[child] < this.heap[child + 1]) child++;
      if (temp >= this.heap[child]) break;
      this.heap[pos] = this.heap[child];
      pos = child;
    }
    this.heap[pos] = temp;
  }

  size() {
    return this.heap.length - 1;
  }
}

function solution(A, B) {
  var answer = 0;

  const maxHeap = new MaxHeap();
  const minHeap = new MinHeap();

  A.sort((a, b) => b - a);

  for (const b of B) {
    maxHeap.insert(b);
    minHeap.insert(b);
  }

  for (const a of A) {
    if (a < minHeap.show()) {
      minHeap.get();
      answer += 1;
    } else if (a >= maxHeap.show()) {
      minHeap.get();
    } else {
      maxHeap.get();
      answer += 1;
    }
  }

  return answer;
}