[백준] 2922_즐거운 단어 (Javascript)

잭슨·2024년 3월 1일

백준 브루트포스 알고리즘 완전탐색 자바스크립트

알고리즘 문제 풀이

목록 보기

41/130

문제

BOJ2922_즐거운 단어

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim();
const cons = ['A', 'E', 'I', 'O', 'U'];
const vowel = ['B', 'C', 'D', 'F', 'G', 'H', 'J', 'K', 'L', 'M', 'N', 'P', 'Q', 'R', 'S', 'T', 'V', 'W', 'X', 'Y', 'Z'];

let answer = 0;
const index = input.indexOf('_');
if (index === -1) answer = 1; // 빈칸이 존재하지 않는 경우
else recursion(input, index, '');
console.log(answer);

function recursion(s, idx, str) {
    // 빈칸을 모두 채웠으면 조건에 부합하는지 확인
    if (!s.includes('_')) {
        if (isPossible(s)) {
            let temp = 1;
            for (let c of str) {
                if (c === 'A') temp *= 5; // 모음
                else if (c === 'B') temp *= 20; // 자음
                else temp *= 1; // L
            }
            answer += temp;
        }
        return;
    }
    for (let i = idx; i < s.length; i++) {
        if (s[i] === '_') {
            // 빈칸에 모음을 넣는 경우
            s = s.slice(0, i) + 'A' + s.slice(i + 1);
            recursion(s, idx + 1, str + 'A');
            // 빈칸에 자음을 넣는 경우
            s = s.slice(0, i) + 'B' + s.slice(i + 1);
            recursion(s, idx + 1, str + 'B');
            // 빈칸에 L을 넣는 경우
            s = s.slice(0, i) + 'L' + s.slice(i + 1);
            recursion(s, idx + 1, str + 'L');
            return;
        }
    }
}

// '즐거운 단어' 조건에 부합하는지 확인
function isPossible(s) {
    if (!s.includes('L')) return false;
    for (let i = 0; i < s.length - 2; i++) {
        if (cons.includes(s[i]) && cons.includes(s[i + 1]) && cons.includes(s[i + 2])) return false;
        if (vowel.includes(s[i]) && vowel.includes(s[i + 1]) && vowel.includes(s[i + 2])) return false;
    }
    return true;
}

시간 복잡도

처음엔 DP로 푸는 문제인줄 알았지만 다른 분들의 풀이를 보니 완전 탐색 문제였다.
빈칸의 개수를 n이라고 하고, 빈칸 하나마다 자음을 넣는 경우, 모음을 넣는 경우, L을 넣는 경우 이렇게 재귀를 3번 호출하니 시간 복잡도는 $O(3^n)$ 이다. $n\le10$ 이므로 3 $^1$ $^0$ =59,049이고, 따라서 브루트 포스로도 풀수 있는 문제다.

풀이

우선 처음 나오는 빈칸의 인덱스를 찾는다.

const index = input.indexOf('_');

만약 빈칸이 존재하지 않다면, 경우의 수는 한 가지 밖에 없다. (입력으로 들어온 문자열 그대로 출력하는 경우)
만약 빈칸이 존재한다면, 재귀 함수를 실행한다.

if (index === -1) answer = 1; // 빈칸이 존재하지 않는 경우
else recursion(input, index, '');

recursion 함수의 첫 번재 인자로는 문자열이 입력되고, 두 번째 인자로는 빈칸의 인덱스가 전달되고, 세 번째 인자로는 재귀를 반복하며 빈칸에 들어갈 문자들이 전달될 예정이다.

recursion 함수의 내부에서는 빈칸을 확인하며 빈칸에 모음을 삽입한 경우, 자음을 삽입한 경우, L을 삽입한 경우를 모두 확인해주는 작업을 한다. 이 때 나는 모음을 넣는 경우를 확인하기 위한 문자로 알파벳 'A'를, 자음을 넣는 경우를 확인하기 위한 문자로는 알파벳 'B'를 골랐다.

function recursion(s, idx, str) {
  
    . . .
    
    for (let i = idx; i < s.length; i++) {
        if (s[i] === '_') {
            // 빈칸에 모음을 넣는 경우
            s = s.slice(0, i) + 'A' + s.slice(i + 1);
            recursion(s, idx + 1, str + 'A');
            // 빈칸에 자음을 넣는 경우
            s = s.slice(0, i) + 'B' + s.slice(i + 1);
            recursion(s, idx + 1, str + 'B');
            // 빈칸에 L을 넣는 경우
            s = s.slice(0, i) + 'L' + s.slice(i + 1);
            recursion(s, idx + 1, str + 'L');
            return;
        }
    }
}

입력값으로 V__K 라는 문자열이 들어왔다고 가정해보자.
처음으로 등장한 빈칸의 인덱스는 1이고, s[1] === '_' 는 true 이므로 if문 안으로 들어온다.
빈칸에 모음을 넣고 재귀를 돈다.

recursion('VA_K', 2, 'A')
recursion('VAAK', 3, 'AA')

빈칸을 모두 채웠으면 그렇게 해서 만들어진 문자열이 '즐거운 단어'인지 확인한다.

function recursion(s, idx, str) {
    // 빈칸을 모두 채웠으면 조건에 부합하는지 확인
    if (!s.includes('_')) {
        if (isPossible(s)) {
            . . .
        }
        return;
    } 
    . . .
}

function isPossible(s) {
    if (!s.includes('L')) return false;
    for (let i = 0; i < s.length - 2; i++) {
        if (cons.includes(s[i]) && cons.includes(s[i + 1]) && cons.includes(s[i + 2])) return false;
        if (vowel.includes(s[i]) && vowel.includes(s[i + 1]) && vowel.includes(s[i + 2])) return false;
    }
    return true;
}

isPossible 함수에서는 해당 문자열이 '즐거운 단어'가 되기 위한 조건에 부합하는지 확인한다.

L이 포함되어 있는가
연속으로 모음이 3번 나오지는 않는가
연속으로 자음이 3번 나오지는 않는가

위 세 조건을 충족하면 true 를 아니라면 false 를 반환한다.

'VAAK'는 'L' 을 포함하지 않기 때문에 즐거운 단어가 될 수 없으므로 false 를 반환한다.

그럼 현재 재귀를 탈출하고 그 다음 재귀를 수행한다.

recursion('VA_K', 2, 'A')
recursion('VABK', 3, 'AB')

또다시 빈칸을 모두 채웠으므로 isPossible 함수를 실행하고, 마찬가지로 'L' 을 포함하지 않으므로 다음 재귀를 수행한다.

recursion('VA_K', 2, 'A')
recursion('VALK', 3, 'AL')

이번엔 L도 포함되었고, 연속으로 자음이나 모음이 3번 반복되지도 않았으므로 아래 코드를 수행해준다.

if (isPossible(s)) {
    let temp = 1;
    for (let c of str) {
      if (c === 'A') temp *= 5; // 모음
      else if (c === 'B') temp *= 20; // 자음
      else temp *= 1; // L
    }
    answer += temp;
}