문제 이해
첫 번째 인자로 문자열 str을, 두 번째 인자로 숫자 num을 받는 JavaScript 함수를 작성해야 합니다.
이 함수는 주어진 문자열 str에 포함된 문자들을 사용하여 정확히 길이가 num인 회문(palindrome) 문자열이 총 몇 개 만들어질 수 있는지 계산한 뒤, 그 개수를 반환해야 합니다.
예를 들어, 입력값이 다음과 같다면 −
const str = 'ij';
const num = 4;
출력은 다음과 같아야 합니다 −
const output = 4;
그 이유는 아래와 같이 네 가지 회문 문자열을 만들 수 있기 때문입니다 −
'iiii', 'jjjj', 'ijji', 'jiij'
접근 방법
먼저 해시 셋(Set)을 활용해 주어진 문자열에 포함된 고유 문자의 개수를 셉니다. 이 값을 u라고 하겠습니다.
회문은 왼쪽 절반이 결정되면 오른쪽 절반이 자동으로 결정되는 대칭 구조이므로, 경우의 수를 효율적으로 계산할 수 있습니다.
- num이 짝수일 때: 왼쪽 절반의 각 자리마다 고유 문자 u개 중 하나를 자유롭게 선택할 수 있으므로, 전체 경우의 수는
u^(num/2)입니다. - num이 홀수일 때: 가운데 문자 역시 고유 문자 중 어느 것이든 올 수 있으므로, 위 값에 u를 한 번 더 곱한
u^(num/2) × u가 됩니다.
코드 구현
다음은 위 로직을 구현한 전체 코드입니다 −
const str = 'ij';
const num = 4;
const findValidPalindromes = (str = '', num = 1) => {
const set = new Set();
for(let i = 0; i < str.length; i++){
const el = str[i];
set.add(el);
};
const u = set.size;
if(num & 1){
return Math.pow(u, num/2) * u;
}else{
return Math.pow(u, num/2);
};
};
console.log(findValidPalindromes(str, num));
출력 결과
콘솔 출력 결과는 다음과 같습니다 −
4
동작 원리 살펴보기
예제에서 문자열 'ij'의 고유 문자는 'i'와 'j' 두 개이므로 u = 2입니다. num이 4(짝수)이므로 2^(4/2), 즉 2² = 4가 반환됩니다. 이는 앞서 나열한 'iiii', 'jjjj', 'ijji', 'jiij' 네 가지 회문과 정확히 일치합니다.
이 접근법은 Set 생성과 문자열 순회에 O(n)의 시간이 걸리고, 계산 자체는 상수 시간에 처리되므로 매우 효율적입니다. 단, num이 커질 경우 결과값이 빠르게 증가하므로 필요에 따라 BigInt 사용이나 모듈러 연산을 함께 고려하면 좋습니다.