바코드 (DFS)

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

• 부분수열 ?
  주어진 수열에서 연속된 모든 구간을 말합니다.
  수열 123의 부분수열은 1, 2, 3, 12, 23, 123 입니다.
• 인접한 두 부분수열 ?
  첫번째 부분수열과 두번째 부분수열이 연속된 경우를 말합니다.
• 만들 수 없는 바코드
  '11'2
  12'3131'2
  '2323'12
  인접한 두 개의 부분 수열이 동일하기 때문에 만들 수 없습니다.

입력
인자 1: len
Number 타입의 1 이상 50 이하의 자연수
출력
String 타입을 리턴해야 합니다.
예시로, 121도, 123도 전부 바코드로 제작할 수 있지만 제일 작은 수는 121이기 때문에 121을 반환해야 합니다.
입출력 예시

let output = barcode(3);
console.log(output); // "121"
output = barcode(7);
console.log(output); // "1213121"
output = barcode(20);
console.log(output); // "12131231321231213123"

function barcode(len) {
  
  // 유효성 검사 함수 -> 부분수열이 중복인지
  function isVaild (str) {
    
    let half = Math.floor(str.length / 2) 
    // 중복을 확인해야하는 최대 자릿수 
    for (let i = 1; i <= half; i++) {
      if (str.slice(-i) === str.slice(2 * -i , -i)) return false;
    } // 바코드는 유효한 바코드 뒤에 수를 덧붙여 생성하기 때문에 
      //덧붙인 수와 기존 바코드의 부분 수열이 중복되지 않는지 확인하면 된다.
    return true;
  }

  // 바코드를 만드는 함수
  function makeBarcode (str) {
    if (str.length === len) return str; 
    // 💡 재귀 탈출의 base case: 원하는 길이의 유효한 바코드
    for (let i = 1; i <= 3; i++) { 
      if (isVaild(str + i)) { 
      // 유효한 바코드에 i를 붙인 것이 유효성 검사를 통과 한다면
        let minBarcode = makeBarcode(str + i)
        if (minBarcode) return minBarcode; 
        // 가능한 것을 찾으면 다른 경우는 찾지말고 바로 반환하라!
        // 이 조건문으로 최소값을 리턴할 수 있다!!
      }
    }
  }
  return makeBarcode('1') // 가장 작은 수의 유효한 바코드에서부터 바코드를 만든다.
}

TIL
코드 작성 전, 문제의 예시를 뜯어보고 규칙을 찾은 후에 로직을 짜자!
뭔가를 이어서 결과를 찾는다? 경로의 정보가 필요한 DFS

• 로직 방향

// 문제 접근 시, 유효성 검사와 재귀를 구현 파트를 나눠 생각해야한다.
if (재귀 탈출 조건) return 문제가 원하는 값
for (let i ~) {
  // 기존 결과에 +X 추가하려고 한다.
  if (유효성 검사(result + X)) {
    let 탈출 가능한 값 = 재귀함수(result + X)
    if (탈출 가능한 값) return 탈출 가능한 값
  } 
}