[백준/JS] 2661 좋은 수열

문제 링크: https://www.acmicpc.net/problem/2661

2661번: 좋은수열

 

백트레킹 문제였다.

1. dfs 를 사용하여 '1', '2', '3' 문자를 추가한다.
2. 좋은 수열인지 아닌지 판별한다. (checkDuplicate)
2-1. 예를 들어 123123 이라는 값이 들어왔다고 가정을 해보자.
2 3
31 23
123 123
맨뒤 인덱스-1 부터 에서 수열의 길이 / 2 까지 구간을 나누어 확인을 한다. 
2-2. 위 방법을 사용할때 좋은 수열이 아닌 값들은 pruning 될 것으므로 맨뒤에 추가된 문자에 대해서만 체크를 하면된다.
3. 현재 1 , 2 , 3 순서대로 문자를 추가 하고 있고 문제에서 최소값을 찾고있다. DFS 특징과 1,2,3 대로 문자를 추가한다는 것이 합쳐져 가 장 처음 찾는 값이 최소값이 된다.
4. flag 변수를 두어 답을 찾으면 나머지 재귀는 탐색하지 않는다.

 

const fs = require('fs');

BOJkey = false;

let input = fs
  .readFileSync(BOJkey ? './javascript/2661/input.txt' : './dev/stdin')
  .toString()
  .trim();

const N = Number(input);
let flag = false;

const checkDuplicate = str => {
  const len = str.length;
  const searchRange = parseInt(len / 2, 10);

  for (let i = 1; i <= searchRange; i++) {
    if (str.slice(len - i, len) === str.slice(len - 2 * i, len - i)) return true;
  }

  return false;
};

const dfs = (L, str) => {
  if (flag) return;

  if (checkDuplicate(str)) return;

  if (L === N) {
    console.log(str);
    flag = true;
    return;
  }

  dfs(L + 1, str + '1');
  dfs(L + 1, str + '2');
  dfs(L + 1, str + '3');
};

dfs(0, '');