두 개의 문자열 str1과 str2를 인자로 받는 JavaScript 함수를 작성해야 합니다.
str1의 길이는 항상 str2보다 길다는 조건이 주어집니다. 우리가 찾아야 할 것은 str2에 포함된 모든 문자를 하나 이상씩 담고 있는 str1 내부의 가장 짧은 연속 부분 문자열입니다.
문제 예시
예를 들어 입력 문자열이 다음과 같다면 −
const str1 = 'abcdefgh';
const str2 = 'gedcf';
출력 결과는 다음과 같아야 합니다 −
const output = 'cdefg';
'cdefg'는 str2('gedcf')의 모든 문자인 g, e, d, c, f를 포함하는 str1의 가장 짧은 연속 부분 문자열이기 때문입니다.
해결 접근 방식
이 문제는 브루트 포스(Brute Force) 방식으로 해결할 수 있으며, 핵심 로직은 다음 두 함수로 구성됩니다.
- subIncludesAll 함수: 특정 부분 문자열이
str2의 모든 문자를 포함하는지 검사합니다. 부분 문자열의 각 문자를 순회하면서str2에 해당 문자가 존재하면 하나씩 제거하고, 최종적으로str2가 빈 문자열이 되면 모든 문자를 포함한 것으로 판단합니다. - minWindow 함수: 이중 반복문을 사용하여
str1에서 만들 수 있는 모든 부분 문자열을 생성하고, 각각이 위 조건을 만족하는지 확인한 뒤 그중 가장 짧은 문자열을 반환합니다.
코드 구현
다음은 전체 코드입니다 −
const str1 = 'abcdefgh';
const str2 = 'gedcf';
const subIncludesAll = (str, str2) => {
for (let i = 0; i < str.length; i++) {
if (str2.indexOf(str[i]) !== -1) {
str2 = str2.replace(str[i], '');
};
};
return (str2.length === 0);
};
const minWindow = (str1 = '', str2 = '') => {
let shortestString = null;
for (let i = 0; i < str1.length; i++) {
for (let j = i; j < str1.length; j++) {
let testString = str1.substr(i, j-i+1);
if (subIncludesAll(testString, str2)) {
if (shortestString === null || testString.length < shortestString.length) {
shortestString = testString;
}
}
}
}
return shortestString;
};
console.log(minWindow(str1, str2));
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다 −
cdefg
참고 사항
위 방식은 모든 부분 문자열을 일일이 검사하기 때문에 시간 복잡도가 O(n³) 수준으로 비효율적일 수 있습니다. 문자열의 길이가 길어지면 성능 저하가 발생할 수 있으므로, 실무나 코딩 테스트에서는 슬라이딩 윈도우(Sliding Window) 기법과 해시 맵(Hash Map)을 함께 활용하면 O(n) 시간 복잡도로 최적화할 수 있습니다.