이번 글에서는 문자열 배열과 하나의 기준 문자열을 인자로 받아, 배열의 요소 중에 기준 문자열의 부분 수열(subsequence)에 해당하는 요소가 존재하는지 판별하는 함수를 작성해 보겠습니다. 조건을 만족하는 요소가 있으면 true, 없으면 false를 반환하는 것이 목표입니다.
문제 이해하기
예를 들어 기준 문자열이 'ACBC'일 때 다음과 같은 결과가 나와야 합니다.
const x = 'ACBC';
const arr = ['cat','AB'];
const arr2 = ['cat','234','C'];
const arr3 = ['cat','CC'];
const arr4 = ['cat','BB'];
console.log(containsString(arr, x)); // true ('AB'는 'ACBC'에서 만들 수 있는 조합)
console.log(containsString(arr2, x)); // true ('C'는 'ACBC'에 포함됨)
console.log(containsString(arr3, x)); // true ('CC'는 'ACBC'에서 만들 수 있는 조합)
console.log(containsString(arr4, x)); // false ('BB'는 'ACBC'로 만들 수 없음)
'AB'나 'CC'처럼 기준 문자열에서 문자를 순서대로 골라 만들 수 있는 조합이라면 true여야 하고, 'BB'처럼 존재하지 않는 문자를 포함하거나 개수가 초과되는 조합이라면 false여야 합니다.
접근 방법: 정렬 후 포함 여부 확인
가장 간단한 방법은 두 문자열을 모두 글자 단위로 분리한 뒤 알파벳 순으로 정렬하고, 배열 요소의 정렬 결과가 기준 문자열의 정렬 결과 안에 포함되는지 확인하는 것입니다. 정렬된 상태에서는 복잡한 부분 수열 문제가 단순한 "문자열 포함" 문제로 바뀌기 때문입니다.
먼저 모든 문자열에서 재사용할 수 있도록 String 프로토타입에 splitSort 헬퍼 메서드를 추가합니다.
const splitSort = function () {
return this.split("").sort().join("");
};
String.prototype.splitSort = splitSort;
이제 메인 함수인 containsString을 작성합니다.
const containsString = (arr, str) => {
const sorted = str.splitSort(); // 기준 문자열을 정렬
for (let i = 0; i < arr.length; i++) {
const sortedEl = arr[i].splitSort(); // 배열의 각 요소를 정렬
if (sorted.includes(sortedEl)) { // 정렬된 기준 문자열에 포함되는지 확인
return true;
}
}
return false;
};
전체 코드 및 실행 결과
const x = 'ACBC';
const arr = ['cat','AB'];
const arr2 = ['cat','234','C'];
const arr3 = ['cat','CC'];
const arr4 = ['cat','BB'];
const splitSort = function () {
return this.split("").sort().join("");
};
String.prototype.splitSort = splitSort;
const containsString = (arr, str) => {
const sorted = str.splitSort();
for (let i = 0; i < arr.length; i++) {
const sortedEl = arr[i].splitSort();
if (sorted.includes(sortedEl)) {
return true;
}
}
return false;
};
console.log(containsString(arr, x)); // true
console.log(containsString(arr2, x)); // true
console.log(containsString(arr3, x)); // true
console.log(containsString(arr4, x)); // false
콘솔 출력
true true true false
동작 원리 자세히 살펴보기
- split(""): 문자열을 한 글자씩 분리해 배열로 만듭니다. 예:
'ACBC'→['A','C','B','C'] - sort(): 분리된 문자들을 알파벳 순으로 정렬합니다. 예:
['A','B','C','C'] - join(""): 정렬된 문자들을 다시 하나의 문자열로 합칩니다. 예:
'ABCC' - includes(): 정렬된 배열 요소가 정렬된 기준 문자열 안에 연속적으로 포함되어 있는지 확인합니다.
기준 문자열 'ACBC'를 정렬하면 'ABCC'가 됩니다. 'AB'를 정렬한 결과는 'AB', 'CC'를 정렬한 결과는 'CC'이므로 둘 다 'ABCC'에 포함되어 true를 반환합니다. 반면 'BB'를 정렬한 'BB'는 'ABCC'에 포함되지 않으므로 false가 반환됩니다.
마무리
이 방식은 코드가 짧고 직관적이라는 장점이 있습니다. 다만 문자열마다 정렬이 수행되므로, 문자열 길이를 n이라 할 때 시간 복잡도는 대략 O(n log n) 수준입니다. 더 나은 성능이 필요하다면 각 문자의 등장 횟수를 미리 세어 비교하는 카운팅 방식으로 최적화할 수도 있습니다.