[Algorithm] 백준 5904 Moo 게임 - node.js

이 글은 백준 5904 Moo 게임 문제를 풀이한다. 코드는 javascript로 작성되었다.

문제

Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다.

Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다.

m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o

Moo 수열은 다음과 같은 방법으로 재귀적으로 만들 수 있다. 먼저, S(0)을 길이가 3인 수열 "m o o"이라고 하자. 1보다 크거나 같은 모든 k에 대해서, S(k)는 S(k-1)과 o가 k+2개인 수열 "m o ... o" 와 S(k-1)을 합쳐서 만들 수 있다.

S(0) = "m o o"
S(1) = "m o o m o o o m o o"
S(2) = "m o o m o o o m o o m o o o o m o o m o o o m o o"

위와 같은 식으로 만들면, 길이가 무한대인 문자열을 만들 수 있으며, 그 수열을 Moo 수열이라고 한다.

N이 주어졌을 때, Moo 수열의 N번째 글자를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 10^9)이 주어진다.

예제 입력 1

11

출력

N번째 글자를 출력한다.

m

풀이

접근

무식하게 풀 수 있을까?

이 문제에서 무식하게 푸는 방법이란, N번째 글자를 포함하는 S(n)을 만든 후 글자를 출력하는 방법일 것이다. 그러나 이 방법으로 문제를 풀게 되면 문자열의 길이가 너무 길어져 채점했을 때 RangeError 결과가 나온다.

그래서 S(n)에 해당하는 문자열을 만드는 방법 대신, S(n)이 만들어지는 데에 참고된 앞의 수열들을 이용해 답을 얻으려고 시도했다.

알고리즘

1. n번째 글자를 포함하는 수열 S(k)가 나올 때까지 수열 S(i)(i=0, 1..., k)의 길이를 모두 저장한다.

2. i=k부터 0까지 차례로 반복문을 돌며 다음 과정을 반복한다.

   S(k)=S(k-1)+'m'+'o'*(k+2)+S(k-1)이므로, n번째 글자가

   • 앞의 S(k-1)에 포함될 때: continue
   • S(k-1) 뒤의 m일 때: m 출력하고 break
   • S(k-1) 앞의 o 중 하나일 때: o 출력하고 break
   • 뒤의 S(k-1)일 때: S(k-1)에서 글자를 파악해야 하므로 n을 n-(|S(k-1)|+k+3)으로 대체, continue

구현

코드

const input = [];
const sLengthList = [];

require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", function (line) {
    input.push(line.trim());
  })
  .on("close", function () {
     const N = Number(input[0]);

     //첫 번째 수열의 길이 삽입
     sLengthList.push(3);

     //N번째 글자를 가지는 수열 S(n)이 나올 때까지 수열의 길이 저장
     while(N>sLengthList[sLengthList.length-1]){
        sLengthList.push(2*sLengthList[sLengthList.length-1]+sLengthList.length+3);
     }

     let n=N;
     for(let i=sLengthList.length-1; i>=0; i--){
         //이전 수열의 길이, i가 0일 때 이전 수열 없으므로 그때 0을 저장
         const prevSLength = (sLengthList[i-1]||0);

         //S(n)=S(n-1)+'m'+'o'*(n+2)+S(n-1)
         if(n===prevSLength+1){
             //S(n-1) 뒤의 m일 때       
             console.log('m');
             break;
         }else if(n>prevSLength+1 && n<=prevSLength+(i+3)){
             //S(n-1) 앞의 o 중 하나일 때  
             console.log('o')
             break;
        }else if(n>prevSLength+(i+3)){
             //뒤의 S(n-1)일 때
             //이전 수열에서 n번째 글짜를 파악하기 위해 n 업데이트
             n-=prevSLength+(i+3);
        }
     }

  });