💡문제 분석 요약

• 주어진 n에 대해 수열을 생성하고, 유효한 조건을 만족하는 수열 중에서 가장 작은 수를 찾아야 한다.
• 수열이 유효한지 판단하기 위해서는 현재 수열에 추가할 숫자가 이전에 추가된 숫자들과 어떻게 연결되는지를 고려해야 한다.

💡알고리즘 설계

• 재귀 백트래킹
  • 현재 수열의 길이가 n이 될 때까지 숫자를 추가한다.
  • 각 숫자를 추가하기 전에 유효성을 체크한다.
    • 같은 숫자가 3번 이상 연속으로 있는지 확인한다.
    • 부분 수열이 1, 2, 3으로 이루어져 있는지 확인한다.
• 유효성 검사
  • 수열의 마지막 2개의 숫자와 추가하려는 숫자를 비교하여 연속된 숫자가 3개가 되는지 확인한다.
  • 수열의 마지막 2개 숫자와 현재 수열에서 1, 2, 3이 연속으로 있는지 확인한다.
• 기저 사례
  • 수열의 길이가 n이 되었을 때, 현재 수열을 결과로 반환한다.

💡코드

const fs = require('fs');
const path = require('path');

const input = fs.readFileSync(path.join(__dirname, 'input.txt')).toString().trim();

const n = parseInt(input, 10); 

function isValid(sequence) {
    const len = sequence.length;

    // 같은 숫자가 3번 이상 연속인지 확인
    if (len >= 3 && sequence[len - 1] === sequence[len - 2] && sequence[len - 2] === sequence[len - 3]) {
        return false;
    }

    // 부분 수열 중 1, 2, 3이 연속인지 확인
    if (len >= 3) {
        const lastThree = sequence.slice(-3);
        if (lastThree[0] !== lastThree[1] && lastThree[1] !== lastThree[2] && lastThree[0] !== lastThree[2]) {
            return false;
        }
    }

    return true;
}

function findGoodSequence(n, sequence = []) {
    if (sequence.length === n) {
        return sequence.join('');
    }

    for (let i = 1; i <= 3; i++) {
        sequence.push(i);
        if (isValid(sequence)) {
            const result = findGoodSequence(n, sequence);
            if (result) {
                return result;
            }
        }
        sequence.pop();
    }

    return null;
}

console.log(findGoodSequence(n));

💡시간 복잡도

• 시간 복잡도는 O(3^n)이다.
  • 수열의 길이가 n일 때, 각 위치에 1, 2, 3 중 하나를 선택할 수 있는 경우의 수가 3개이기 때문이다.
  • 유효성 검사 과정에서 불필요한 경로를 차단하므로 실제 시간은 이보다 더 적을 수 있다.