JavaScript에서 문자열과 양의 정수 n을 인자로 받아, 문자열 내 모든 문자가 최소 n번 이상 등장하는 가장 긴 부분 문자열(substring)의 길이를 구하는 함수를 작성하는 방법을 알아보겠습니다.
문제 이해하기
주어진 문자열에는 반복되는 문자들이 포함될 수 있습니다. 우리가 구해야 하는 것은 원본 문자열의 부분 문자열 중에서, 포함된 모든 문자가 각각 최소 n번 이상 나타나는 부분 문자열의 최대 길이입니다.
예를 들어 입력이 다음과 같다고 가정해 보겠습니다.
const str = 'kdkddj';
const num = 2;이 경우 기대되는 출력은 다음과 같습니다.
const output = 5;문자열 'kdkddj'에서 'k'는 2번, 'd'는 3번, 'j'는 1번 등장합니다. 'j'는 2번 미만으로 등장하므로 조건을 만족하지 못하고, 따라서 'j'를 제외한 'kdkdd'가 조건을 충족하는 가장 긴 부분 문자열이며 그 길이는 5입니다.
해결 접근 방식
이 문제는 재귀적 분할 정복 방식으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 문자열 내 각 문자의 빈도수를 계산합니다.
- 빈도수가 가장 낮은 문자를 찾습니다. 만약 이 문자조차 n번 이상 등장한다면, 문자열의 모든 문자가 조건을 만족하는 것이므로 전체 길이를 그대로 반환합니다.
- 그렇지 않다면, 조건을 위반하는 문자를 기준으로 문자열을 분할하고, 각 부분 문자열에 대해 재귀적으로 같은 과정을 수행합니다.
- 재귀 호출 결과들 중 최대값을 최종 답으로 반환합니다.
구현 코드
const str = 'kdkddj';
const num = 2;
const longestSubstring = (str = '', num) => {
// 문자열 길이 자체가 num보다 작으면 조건을 만족할 수 없음
if (str.length < num) {
return 0;
}
// 각 문자의 빈도수 계산
const map = {};
for (let char of str) {
if (char in map) {
map[char] += 1;
} else {
map[char] = 1;
}
}
// 빈도수가 가장 낮은 문자 찾기
const minChar = Object.keys(map).reduce(
(minKey, key) => (map[key] < map[minKey] ? key : minKey)
);
// 최소 빈도 문자조차 n번 이상이면 전체 문자열이 정답
if (map[minChar] >= num) {
return str.length;
}
// 조건 위반 문자를 기준으로 분할 후,
// 길이가 num 이상인 부분만 필터링
const substrings = str.split(minChar).filter((subs) => subs.length >= num);
if (substrings.length === 0) {
return 0;
}
// 각 부분 문자열에 대해 재귀적으로 최대 길이 계산
let max = 0;
for (let ss of substrings) {
max = Math.max(max, longestSubstring(ss, num));
}
return max;
};
console.log(longestSubstring(str, num));실행 결과
5코드 동작 원리 살펴보기
입력 'kdkddj'와 n = 2를 기준으로 코드의 흐름을 단계별로 확인해 보겠습니다.
- 먼저 각 문자의 빈도수를 계산하면 { k: 2, d: 3, j: 1 }이 됩니다.
- 빈도수가 가장 낮은 문자는 'j'(1회)이며, 이 값이 2 미만이므로 전체 문자열은 정답이 될 수 없습니다.
- 'j'를 기준으로 문자열을 분할하면 ['kdkdd', '']가 되고, 길이 조건을 통과한 ['kdkdd']만 남습니다.
- 'kdkdd'에 대해 재귀 호출하면 k: 2, d: 3으로 모든 문자가 2번 이상 등장하므로 길이 5가 반환됩니다.
- 결국 최종 출력은 5가 됩니다.
이처럼 조건을 위반하는 문자를 단계적으로 제거해 가며 탐색 범위를 좁히는 방식 덕분에, 불필요한 모든 부분 문자열을 일일이 검사하는 완전 탐색보다 훨씬 효율적으로 답을 구할 수 있습니다.