<Demopeu/>

[백준] 14891 톱니바퀴 JavaScript / [백준] 15662 톱니바퀴 2 JavaScript

[백준] 14891 톱니바퀴 JavaScript / [백준] 15662 톱니바퀴 2 JavaScript

problem-solving백준구현시뮬레이션

📌 문제 설명

톱니바퀴 문제 보기

톱니바퀴 2 문제 보기

📌 문제 접근

시뮬레이션 동시성을 물어보는 문제. 현실에서 동시에 맞물려 돌아가기 때문에, 먼저 돌려버리면 오답이 나올 확률이 높고, 디버깅이 힘들다. 한 번에 처리해야 하는지 알아채는 2가지 판별법이 있다.

1. "동시에 일어난다"

문제 지문에 "동시에", "한 번의 턴에", "하루가 지날 때" 같은 말이 있으면 보통 동시성을 물어보는 문제이다.

2. "A의 변화가 B의 조건 검사에 영향을 줄 때"

1번 기어를 먼저 돌려버리면 2번 기어는 과거의 1번이 아닌 이미 돌아가버린 미래를 기준으로 비교하기 때문에 상태 오염이 발생한다.

함수 작성 순서

컴포넌트 마냥 제일 작은 단위부터 짜는 것이 좋다.

  1. 가장 작은 단위 액션 : 톱니 1개 돌리기
  2. 상태 명세 작성: 어떤 조건일 때 기본 단위를 실행할 것인가? -> 극성이 다를 때 -> 명세를 작성해서 상태를 고정
  3. 명령을 하나씩 꺼내면서 2번을 호출한다.
  4. 결과 정산

📌 내가 작성한 코드

1.톱니바퀴

const input = require("fs").readFileSync(0).toString().trim().split(/\s+/);

const gear = [
  input[0].split("").map(Number),
  input[1].split("").map(Number),
  input[2].split("").map(Number),
  input[3].split("").map(Number),
];
const k = Number(input[4]);
const works = [];
for (let i = 5; i < input.length; i += 2) {
  works.push([Number(input[i]), Number(input[i + 1])]);
}

const rotate = (gear_idx, dir) => {
  dir === 1
    ? gear[gear_idx].unshift(gear[gear_idx].pop())
    : gear[gear_idx].push(gear[gear_idx].shift());
};

const check_chain_reaction = (startIdx, start_dir) => {
  const dirs = [0, 0, 0, 0];
  dirs[startIdx] = start_dir;
  for (let i = startIdx; i > 0; i--) {
    if (gear[i][6] !== gear[i - 1][2]) dirs[i - 1] = -dirs[i];
    else break;
  }
  for (let i = startIdx; i < 3; i++) {
    if (gear[i][2] !== gear[i + 1][6]) dirs[i + 1] = -dirs[i];
    else break;
  }
  return dirs;
};

for (const [n, d] of works) {
  const start_idx = n - 1;
  const dirs = check_chain_reaction(start_idx, d);
  for (let i = 0; i < 4; i++) {
    if (dirs[i] != 0) rotate(i, dirs[i]);
  }
}

console.log(gear[0][0] * 1 + gear[1][0] * 2 + gear[2][0] * 4 + gear[3][0] * 8);

2.톱니바퀴2

const fs = require("fs");
const input = fs.readFileSync(0).toString().trim().split(/\s+/);

let [t, ...etc] = input;
const gears = [];
const play = [];
t = Number(t);

for (let i = 0; i < t; i++) {
  gears.push(etc[i].split("").map(Number));
}
const k = Number(etc[t]);
for (let i = t + 1; i < etc.length; i += 2) {
  play.push([Number(etc[i]), Number(etc[i + 1])]);
}

const rotate = (gear_idx, dir) =>
  dir === 1
    ? gears[gear_idx].unshift(gears[gear_idx].pop())
    : gears[gear_idx].push(gears[gear_idx].shift());

const make_dirs = (start_idx, start_dir) => {
  const dirs = Array.from({ length: t }, () => 0);
  dirs[start_idx] = start_dir;
  for (let i = start_idx; i > 0; i--) {
    if (gears[i][6] === gears[i - 1][2]) break;
    dirs[i - 1] = -dirs[i];
  }
  for (let i = start_idx; i < t - 1; i++) {
    if (gears[i][2] === gears[i + 1][6]) break;
    dirs[i + 1] = -dirs[i];
  }
  return dirs;
};

for (const [r, c] of play) {
  const dirs = make_dirs(r - 1, c);
  for (let i = 0; i < t; i++) {
    if (dirs[i] !== 0) rotate(i, dirs[i]);
  }
}

console.log(gears.reduce((acc, cur) => (acc += cur[0]), 0));

📌 시간 복잡도

  • 톱니바퀴 1: O(K × 4) = O(K)
  • 톱니바퀴 2: O(K × T) = O(KT)

📌 참고 링크