문제 개요

문제: 공항

분류: 자료 구조, 그리디 알고리즘, 분리 집합

난이도: 골드2

문제 풀이

g가 주어졌을 때, 최대한 많은 비행기를 도킹하기 위해 g번부터 1번까지 도킹을 시도한다.

예를 들어 g가 4라면 1번~4번 게이트 중 하나에 도킹할 수 있다.
일단 4번에 도킹이 가능한지를 살피고 안된다면 3번, 또 안된다면 2번, 마지막으로 1번을 시도하는 식이다.

이를 일반 반복문으로 처리하면 매번 g부터 전부 살피기 때문에 시간 초과가 발생할 수 있다. 게이트의 개수가 최대 10만개이고 도킹하려는 비행기의 개수 또한 최대 10만개이므로 최악의 경우 반복문을 100억번 수행할 수 있다.

그래서 Union-Find 알고리즘을 사용했다.

처음에는 모든 게이트의 루트가 자기 자신으로 초기화되어 있다.
만약 g번 게이트에 도킹한다면, 다음에 g번에 도킹하려는 비행기는 g-1번에 도킹이 가능하다.

이를 표현하기 위해 g번 게이트에 도킹한 이후 g번 게이트의 루트 r을 찾아 r의 루트를 r-1의 루트로 업데이트 한다. 즉 Find를 통해 g의 루트 r을 찾고, r과 r-1을 Union 한다.

정리하자면 아래와 같다.

1. 모든 게이트의 루트를 자기 자신으로 초기화한다.
2. 비행기를 도킹하려는 모든 게이트 g에 대해 아래를 수행한다.
   • g의 루트가 0이라면, 1번~g번까지 전부 비행기가 도킹되어 있다는 뜻이므로 반복문을 종료한다.
   • g의 루트가 0이 아니라면, g의 루트 r을 Find 하여 r과 r-1을 Union 하고 정답 변수를 증가시킨다.
3. 정답 변수를 출력한다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const [G, P, ...gate] = fs.readFileSync(filePath).toString().trim().split("\n");
const root = Array.from({ length: +G + 1 }, (_, i) => i);

const find = (x) => {
  if (x === root[x]) return x;
  return (root[x] = find(root[x]));
};

const union = (x, y) => {
  x = find(x);
  y = find(y);
  if (x != y) root[y] = x;
};

const solution = () => {
  let answer = 0;

  for (let g = 0; g < gate.length; g++) {
    let r = find(+gate[g]);

    if (r <= 0) break;
    union(r - 1, r);
    answer++;
  }

  console.log(answer);
};

solution();