[바미] 재귀의 귀재

문제

https://www.acmicpc.net/problem/25501

 

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const T = parseInt(input[0], 10);
const cases = input.slice(1);

function recursion(s, l, r, count) {
    count.count++;
    if (l >= r) return [1, count.count];
    else if (s[l] !== s[r]) return [0, count.count];
    else return recursion(s, l + 1, r - 1, count);
}

function isPalindrome(s) {
    let count = { count: 0 };
    return recursion(s, 0, s.length - 1, count);
}

let results = [];

for (let i = 0; i < T; i++) {
    const [isPal, callCount] = isPalindrome(cases[i]);
    results.push(`${isPal} ${callCount}`);
}

console.log(results.join('\n'));

문제 해설

재귀 함수를 사용하여 문자열이 팰린드롬인지 확인하고, 재귀 함수 호출 횟수를 세는 문제입니다.

 

이 문제를 해결하기 위해서 재귀 함수를 사용하여 문자열이 팰린드롬인지 확인하는 함수를 작성한 뒤, 각 재귀 호출 시 호출 횟수를 세는 방법을 추가하여 각 테스트 케이스에 대해 결과를 출력하면 됩니다.

 

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

재귀적 팰린드롬 검사 함수의 시간 복잡도는 𝑂(𝑛))입니다. 여기서 𝑛은 문자열의 길이를 의미 합니다.
그리고 각 문자열에 대해 한 번의 재귀 호출을 수행하므로 총 시간 복잡도는 𝑂(𝑇×𝑛)가 됩니다.
여기서 𝑇는 테스트 케이스의 개수를 의미합니다.

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

재귀 호출 스택의 깊이는 문자열의 길이 𝑛이므로 공간 복잡도는 𝑂(𝑛)이 되고, 각 테스트 케이스에 대해 별도의 결과 배열을 사용하므로 추가 공간은 𝑂(𝑇)이 되기 때문에 총 공간 복잡도는 𝑂(𝑇 + 𝑛)이 됩니다.