백준1590 - 캠프가는 영식 (완전탐색) node.js

https://www.acmicpc.net/problem/1590

해당 문제는 N개의 버스, 버스터미널에 도착하는 시간 T, 그리고 각각의 버스의 시작 시간, 간격, 대수가 주어진다고 할 때, 가장 빨리 갈 수 있는 버스를 타기 위해 기다려야 하는 시간을 출력하는 문제다.

 

문제 해결 방식

이분탐색 문제로 구성되어 있었지만, 완전탐색으로 가능할 것 같아 완전탐색으로 해결했다.

버스 스케쥴을 하나씩 순회하는 과정에서 가장 늦는 버스 시간이 버스 터미널 도착시간보다 이를 경우, 패스하는 과정을 넣어 시간복잡도를 단축시켰다.

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  const [[_, T], ...arr] = data.map((el) => el.split(" ").map(Number));
  let result = Infinity;

  for (let i = 0; i < arr.length; i++) {
    const [s, l, c] = arr[i];
    // 마지막에 도착하는 버스가 터미널 도착시간보다 빠른 경우 패스
    if (T > s + l * (c - 1)) continue; 

    for (let j = 0; j < c; j++) {
      const temp = s + l * j; // 버스 출발 시간
      if (temp >= T) { // 탈 수 있는 가장 빠른 버스를 찾은 경우 result 재할당
        result = Math.min(result, temp);
        break;
      }
    }
  }

  console.log(result === Infinity ? -1 : result - T);
}

solution(input);