코플릿_[DFS] 바코드

문제

1, 2, 3으로만 이루어진 수열 바코드를 만들어야 합니다. 바코드에서 인접한 두 개의 부분 수열이 동일하다면 제작할 수 없다고 할 때, 주어진 길이 len의 바코드 중 가장 작은 수를 반환하는 함수를 작성하세요.

입출력 예시

let output = barcode(3);
console.log(output); // "121"

output = barcode(7);
console.log(output); // "1213121"

output = barcode(20);
console.log(output); // "12131231321231213123"

입력

Number 타입의 1 이상 50 이하의 자연수

출력

String 타입 리턴

풀이

function barcode(len) {
  
  const isValid = (str) => {
    // 
    const reversed = str.split('').reverse().join('');
    // 최대 절반 길이만큼의 부분 수열이 가능
    const halfLen = Math.floor(str.length / 2); 
    for (let i = 1; i <= halfLen; i++) {
      if (reversed.slice(0, i) === reversed.slice(i, i + i)) {
        return false; // 인접한 부분 수열이 동일
      }
    }
    return true;
  }
  
  const chr = '123'; // 바코드 조건
  
  const aux = (str) => {
    if (str.length === len) return str;
    for (let i = 0; i < chr.length; i++) { 
      if(isValid(str + chr[i])) {
        const founded = aux(str + chr[i]);
        if (founded !== null) {
          return founded;
        }
      }  
    }
    return null // 모두 false인 경우
  }
  
  return aux(''); // 초기값
}

console.log(barcode(5)) // "12131"

str	reversed	if	isValid
"1"	"1"	-	true
"11"	"11"	("1" === "1")	false
"12"	"21"	("2" === "1")	true
"121"	"121"	("1" === "2")	true
"1211"	"1121"	("1" === "1")	false
"1212"	"2121"	("21" === "21")	false
"1213"	"3121"	("31" === "21")	true
"12131"	"13121"	("13" === "12")	true