[DFS] 바코드

 

 

문제

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) {
    const isValid = (str) => {
        // index 관리를 편하게 하기 위해 string reverse
        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;
        // 모든 길이에 대해서 순차적으로 유효성을 검사하기 때문에,
        // str.length 보다 낮은 길이의 str은 이미 유효성을 통과했다.
        // 따라서 처음부터 시작하는 부분 수열만 고려해도 된다. (reverse 된 상태라고 가정)
        // 예시. 문자열이 '123123'일 경우
        // 예시. ('1', '2'), ('12', '31'), ('123', '123')
        // 인덱스 1에서 시작하는 부분 수열을 검사할 필요가 없는데,
        // 예시. ('2', '3'), ('23', '12'), ...
        // 이는 이미 이전 문자열이 '32132' 에서 검토되었기 때문인다. '32132'를 뒤짚으면 '23123'
    }
    const chr = '123';
    const aux = (str) => {
        // 유효성을 통과해서 만든 길이 len의 str을 리턴한다.
        if (str.length === len) return str;
        // 조건을 만족하는 가장 작은 수를 찾고 있으므로,
        // 1, 2, 3 순서대로 검토한다.
        // 실제 수(number) 비교는 필요없다.
        for (let i = 0; i < chr.length; i++) {
            if(isValid(str + chr[i])) {
                const founded = aux(str + chr[i]);
                if (founded !== null) return founded;
            }  
        }
        // 현재 str에서 1, 2, 3을 이어붙여서 유효한 문자열을 만들 수 없는 경우
        return null
    }
    return aux('');
}