[Algorithm] 바코드 문제 DFS 알고리즘 기초 Javascript

 

 

문제

 

1,2,3 으로만 구성된 수열 바코드를 생성해야 한다. 무조건 1,2,3만 붙여서 바코드를 만들면 쉽겠지만, 조건이 붙어있다. 바코드에서 인접한 두개의 부분 수열이 동일한 경우 바코드로 제작할 수 없다. 입력값으로는 바코드의 길이 len이 주어진다. 생성 가능한 바코드 중 가장 작은 바코드를 반환하라.

 

생성 불가능한 바코드

• 112
• 12311231
• 123131
• 1212

 

부분 수열이란 주어진 수열에서 연속된 모든 구간을 의미한다. 인접한 두 부분 수열이란 첫번째 부분 수열과 두번째 부분 수열이 연속된 경우를 의미한다. 자릿수에 상관없이 인접한 부분 수열이 같은 경우 바코드를 생성할 수 없다. 

 

출력 예시

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

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

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

 

 

소스코드 해설

 

문제는 생성가능한 바코드를 물어보고 있지만 알고리즘 적으로 생각해보면 DFS 알고리즘을 구현하는 문제다. 문제에서 제시한 제약 조건은 2가지다.

 

제약조건

• 연결가능한 요소 중 작은 요소를 선택하라
• 인접한 부분 수열을 제거하라

 

예를 들어 길이가 5개인 바코드를 생성한다고 했을 때 모든 경우의 수를 Tree 자료구조로 표현할 수 있다.

 

알고리즘을 풀어서 이해해보면 연결가능한 요소 중 작은 요소 순서로 새로운 요소가 추가될 때 인접한 부분 수열이 존재하는지 확인 한 후 만약 인접한 부분 수열이 존재하지 않는 경우 새로운 요소를 추가한다. 다음 단계로 넘어간다.

 

트리 구조로 확인해보면 이번 문제가 명확히 DFS 알고리즘이라는 것을 확인할 수 있다. 루트 노드 부터 단말 노드까지 내려가면서 제약 조건을 충족한 경우의 수를 반환한다.

 

 

유효성 검사 함수

인접한 부분 수열이 존재하는지 확인하기 위해 유효성 검사 함수를 생성해야 한다. 새로운 요소를 추가한 str을 입력값으로 받아 최대 검사해야 하는 횟수(문자열의 길이 / 2) 만큼 반복문을 수행한다.

 

예를 들어 1212가 입력값으로 주어지는 경우

• case 1) : 2와 1을 비교한다.(가장 뒤의 값과 2번째 뒤의 값)
• case 2) : 12와 12를 비교한다.(가장 뒤에서 2개, 그 다음 뒤에서 2개)

만약 인접한 부분 수열이 존재하는 경우 false를, 존재하지 않는 경우 true를 반환한다.

 

// 유효성 검사 함수
const validCheck = (str) => {

    for(let i=1; i<(str.length)/2+1; i++){
        const r1 = str.slice(str.length-i)
        const r2 = str.slice(str.length-i*2, str.length-i)

        if(r1===r2) return false;
    }
    return true;
}

 

바코드 생성 재귀함수

 

① 바코드를 생성하기 위한 재귀 함수의 탈출 조건은 주어진 n이 바코드의 길이 len과 같아지는 시점이다.

② 연결가능한 요소들은 오름차순 정렬되어 있는 상태다.

③ temp 변수에 새로운 요소를 추가한 str를 유효성 검사를 진행한 뒤 통과하는 경우 새로운 요소를 최종적으로 삽입한다. 

④ 만약 모든 요소에서 유효성 검사가 실패하는 경우 null을 반환한다. 

// 재귀 함수
const recur = (n, str) => {
    if(n === len) return str;
    const available = elements.filter((item)=>item!==str[str.length-1])
    for(let j=0; j<available.length; j++){
        const temp = str+(available[j]);
        if(validCheck(temp)){
            const resVal = recur(n+1, temp)
            if(resVal !== null) return resVal;
        }
    }
    return null;
}

 

함정

문제를 풀다보면 8번째 요소를 선택할 때 문제가 발생한다. 8번째에서 선택 가능한 2와 3 모두 불가능한 숫자이기 때문이다. 따라서 여기서 프로세스를 되돌린 다음 7번째에서 새로운 분기로 넘어가야 한다. 이 경우를 대비해서 재귀 함수의 반환값을 resVal 변수에 저장한 뒤 null이 아닌 경우에 한해서 결과값을 반환한다.

 

 

전체 소스코드

 

function barcode(len) {

    const elements = ['1','2','3'];
    let currentStr = '1';

    // 유효성 검사 함수
    const validCheck = (str) => {

        for(let i=1; i<(str.length)/2+1; i++){
            const r1 = str.slice(str.length-i)
            const r2 = str.slice(str.length-i*2, str.length-i)

            if(r1===r2) return false;
        }
        return true;
    }

    // 재귀 함수
    const recur = (n, str) => {
        if(n === len) return str;
        const available = elements.filter((item)=>item!==str[str.length-1])
        for(let j=0; j<available.length; j++){
            const temp = str+(available[j]);
            if(validCheck(temp)){
                const resVal = recur(n+1, temp)
                if(resVal !== null) return resVal;
            }
        }
        return null;
    }

    return recur(1,currentStr);

}

 

 

 

 

[Algorithm] Advanced Bubble Sort 알고리즘 Javascript

 

[Algorithm] Javascript 인접 행렬(Adjacency Matrix) 생성하기

 

[Algorithm] 시간복잡도 개선 부분집합 문제