문제

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

비행기의 통로가 한개 있고 승객이 N명 존재한다.
승객은 각 열에서 정확히 1초씩 소비하며 앞으로 진행한다.
좌석에 도착하면 5초동안 짐을 놓는데 진행중 다른 승객이 있다면 잠시 멈춘다.

나왔던 반례들

• 탐색하는 위치에 사람이 짐을 넣고있는지 정확하게 체크하지 않았었다
  • 그래서 사람이 짐을 넣고있을때 비행기 밖으로 막 탈출했다!

---

정답코드

const fs = require('fs');
const stdin = fs.readFileSync(0, 'utf-8')
  .trim()
  .split('\n');
const input = (() => {
  let line = 0;
  return () => +stdin[line++]; //.split(' ').map(v => +v);
})();

const solution = () => {
  const p = Array.from({ length: input() }, () => input());
  const q = Array(1001).fill(-1);
  const stayedTime = {};
  let resultTime = -1;

  const loop = condition => {
    let result = 0;
    // 조건이 insert일경우 맨 앞에 넣을수 있는지봄 : q가 전부 -1인지 봄
    while (condition === 'insert' ? q[0] !== -1 : !q.every(v => v === -1)) {
      for (let j = 1000; j > 0; j--) {
        // 만약 현재 위치에서 짐을 싣는중이라면
        if (j === q[j]) {
          // 시간 -1
          stayedTime[j]--;
          // 짐을 전부 실었으면
          if (stayedTime[q[j]] === 0) {
            delete stayedTime[q[j]];
            q[j] = -1;
          }
        }
        // 현재 위치가 비었고// 현재 위치가 5초 지났고// 현재 위치가 내가 가는곳 이하이면
        // 오른쪾으로 옮김
        if (j <= q[j - 1] && q[j] === -1) {
          q[j] = q[j - 1];
          q[j - 1] = -1;
          if (j === q[j]) {
            stayedTime[q[j]] = 5;
          }
        }
      }
      result++;
    }
    return result;
  };

  for (let i = 0; i < p.length; i++) {
    q[0] = p[i];
    // 만약 들어갈 자리가 없다면 생길때까지 만듬.
    resultTime += loop('insert');
  }
  // 모두 자리에 앉을때까지 반복
  resultTime += loop('move');

  return resultTime;
};

console.log(solution());

---

코드설명

처음에는 O(N)의 시간으로 풀어보려고 발악을 했지만 결국 불가능했다.
N이 1,000으로 작아서 처음부터 이렇게 풀면 시간낭비를 하지 않았을것같다.

풀이방법은 현실의 비행기에서 짐을 넣고있을때 사람이 기다리는걸
아래의 세가지 규칙으로 코드를 작성했다.

1. 앞이 비어있다면 한칸 전진한다.
2. 앞에 사람이 있다면 짐을 넣는동안 기다린다.
3. 내 자리에 도착하면 짐을넣는다.

while문에서 탈출초건을 두개로 나눴는데
처음에 사람이 비행기에 들어갈때와 다 들어가고 나서의 조건이 달라서 이렇게 표현했다.

while (condition === 'insert' ? q[0] !== -1 : !q.every(v => v === -1)) {

다음부터는 시간낭비를 하지 말자!