[백준] 5581

碁石ならべ

문제

白と黒の碁石をテーブルの上にならべて遊ぶ．まずテーブルの左端に碁石を置く． 次に左から 2 番目の場所に碁石を置く．これを n 回繰り返して n 個の碁石を横一列 にならべる．ただし，新しく i 番目の碁石を置く際には，次のルールに従ってテー ブル上の碁石を置き換える．

• i が奇数の場合: テーブルに置いてあった碁石は置き換えず，新しい碁石を左 から i 番目に置く．
• i が偶数の場合: 新しく左から i 番目に置く碁石の色とテーブル上の右端の碁 石の色が同じ場合は，テーブル上の碁石は置き換えず，新しい碁石を左から i 番目に置く．そうでない場合，すなわち，新しく左から i 番目に置く碁石の色 とテーブル上の右端の碁石の色が異なる場合は，まずテーブル上の右端の連続 した同色の碁石を全て取り除き，i 番目の碁石と同色の碁石に置き換える．そ してテーブルの右端に i 番目の碁石を置く．

例えば，最初の 7 個の碁石を置いた時点で，

○○●●○○○

となっていたとする．（○は白の碁石を，●は黒の碁石を表す．）

• 8 番目の碁石が白（○）の場合は，右端の碁石と同色なので，そのまま置く．し たがって，テーブル上の碁石は○○●●○○○○となる．
• 8 番目の碁石が黒（●）の場合は，右端の碁石（○）と色が異なるので，まず テーブルの右端にある 3 個の連続した白い碁石（○）を取り除き，黒い碁石 （●）に置き換える．そして右端に 8 番目の碁石を置く．したがって，テーブ ル上の碁石は○○●●●●●●となる．

入力として置く碁石の順番が与えられたとき，n 個の碁石をならべ終わった後，テー ブル上に置いてある白い碁石の個数を求めるプログラムを作成せよ．

입력

1 行目には正整数 n (1 ≤ n ≤ 100000) が書かれている．2 行目以降の第 i + 1 行目 (1 ≤ i ≤ n) には，i 番目に置く碁石の色を表す整数 ci が書かれており，ci が 0 な ら i 番目に置く碁石の色が白であることを，1 なら i 番目に置く碁石の色が黒であ ることを表す．

출력

n 個の碁石をならべ終わった後にテーブル上に置いてある白い碁 石の個数だけを含む 1 行からなる．

풀이

const narabe = () => {
  const fs = require("fs");
  let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
  input.shift();
  input = input.map((n) => {
    return parseInt(n);
  });
  let stack = [];
  let idx = 1;
  let white = 0;

  for (i of input) {
    if (stack.length === 0) stack.push([i, 1]);
    else {
      if (idx % 2 === 0 && stack[stack.length - 1][0] !== i) {
        let tmp = stack.pop()[1];
        if (stack.length > 0) stack[stack.length - 1][1] += tmp;
        else stack.push([i, tmp]);
      }
      if (stack[stack.length - 1][0] === i) stack[stack.length - 1][1]++;
      else stack.push([i, 1]);
    }
    idx++;
  }
  stack.forEach((n) => {
    if (n[0] === 0) white += n[1];
  });
  console.log(white);
};

narabe();

반성회

바둑돌을 죄다 push하고 죄다 pop해버리면 시간 초과가 발생한다

따라서 스택에 바둑돌 숫자만 넣지 말고 배열로 바둑돌이 연속으로 등장하는 개수를 넣어주면 좋음

그러면 짝수번째에 색다른 돌이 나와서 앞에 있는 모든 돌의 색깔을 바꿔줄 때도 배열의 첫 번째 인자값만 업데이트해주면 된다