[알고리즘/javascript] 바코드

문제

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을 반대로 뒤집어준다.
        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'가 되므로).
    }
		
		// 조건을 만족하는 가장 작은 수를 리턴해야하므로 1->2->3 순서대로 검사한다.
    const chr = '123';
    const aux = (str) => {
        // 유효성 검사를 통과해서 만든 str(바코드)의 길이가 len과 같다면 리턴한다.
        if (str.length === len) return str;
        for (let i = 0; i < chr.length; i++) {
					// 유효성 검사를 통과한다면
            if(isValid(str + chr[i])) {
							// BFS(재귀 호출)을 통해 뒤에 숫자를 붙혀가며 조건을 만족하는 바코드를 만들어나간다.
                const founded = aux(str + chr[i]);
                if (founded !== null) return founded;
            }  
        }
        // 현재 str에서 1, 2, 3을 이어붙여서 유효한 문자열을 만들 수 없는 경우에는 null을 리턴해준다.
        return null
    }
		// 재귀호출을 통해 aux('')를 리턴한다. 결국 aux('')의 리턴값이 길이가 len인 바코드 중 가장 작은 수이다.
    return aux('');
}