바코드

문제

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

만들 수 없는 바코드만들 수 있는 바코드

112	1312
1231312	3
232312	231213

• 부분수열? 주어진 수열에서 연속된 모든 구간을 말합니다. 수열 123의 부분수열은 1, 2, 3, 12, 23, 123 입니다.
• 인접한 두 부분수열? 첫번째 부분수열과 두번째 부분수열이 연속된 경우를 말합니다.

• 수열 1234에서 인접한 부분수열 (우리는 두 부분수열이 같은 지 관심이 있으므로 길이가 서로 다른 경우는 무시한다)

  • 1과 2, 2와 3, 3과 4, 12와 34입니다.

• 만들 수 없는 바코드를 보자면,

  • '11'2
  • 12'3131'2
  • '2323'12 인접한 두 개의 부분 수열이 동일하기 때문에 만들 수 없습니다. 고로, '12131213'과 같이 네 자리씩 중복되어도 만들 수 없습니다. 자릿수와 상관없이, 인접한(붙어있는) 부분수열이 같다면 바코드를 만들 수 없습니다.

입력

인자 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) {
  // TODO: 여기에 코드를 작성하세요.
  //len만큼 문자열에 숫자를 추가한다.
  //len이 2이면 '1'+'1' 해보고 check돌려서 true가 나오면 '1'+'2'를 해본다
  //len이 3이면 '11' '12' '121'
  //len이 4이면 '11' '12' '121' '1211' '1212' '1213
  let visited = {}
  let result= ''  
  result = makeCode(result, len, visited)
  console.log(visited)
  return result
  
}
function makeCode(code, len,visited,i =1){
  if(code.length < len){
    if(i > 3){
      let lastNum = code.slice(-1)            
      code = makeCode(code.slice(0,-1), len,visited, Number(lastNum) + 1)
    }
    for(; i<= 3 ; i++){
      code += String(i)      
      if(check(code, visited)){//만들수 없는 바코드
        code = code.slice(0,-1)//마지막꺼를 다시 뺌
        if(i === 3){ //3까지 시도를 해봤지만 전부 안됐음
          let lastNum = code.slice(-1)            
          code = makeCode(code.slice(0,-1), len, visited, Number(lastNum) + 1)
        }   
      }      
      else{//만들수 있는 바코드
        break;
      }      
    }
    return makeCode(code, len,visited, 1)
  }
  return code
}
function check(str, visited){
  //let str = String(num)
  if(visited[str] === undefined){
    let reversed = str.split('').reverse().join('');
    let halfLength = Math.floor(reversed.length /2) 
    for(let i= 1; i <= halfLength; i ++){
      if(reversed.slice(0,i)=== reversed.slice(i, i+i)){
        visited[str] = true
        return true//같은게 있다
      }
    }    
    visited[str] = false
    return false
  }
  else{//방문 했던 곳
    return visited[str]
  }
}

주의할것: migoreng.tistory.com/110