문제 설명
첫 번째 인자로 문자열 str을, 두 번째 인자로 문자열 배열 arr을 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 배열의 각 요소 arr[i] 중에서 str의 부분 수열(subsequence)에 해당하는 개수를 세어 반환해야 합니다.
여기서 부분 수열이란 원본 문자열에서 문자들의 상대적인 순서를 유지하면서 일부 문자를 생략했을 때 얻을 수 있는 문자열을 의미합니다. 반드시 연속된 문자일 필요는 없다는 점이 부분 문자열(substring)과의 차이입니다.
입력 및 출력 예시
예를 들어 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.
입력
const str = 'klmnop';
const arr = ['k', 'll', 'klp', 'klo'];
출력
const output = 3;
출력 설명
'k', 'klp', 'klo'는 모두 'klmnop'의 부분 수열이지만, 'll'은 문자 'l'이 원본 문자열에 하나도 없으므로 부분 수열이 될 수 없습니다. 따라서 결과는 3입니다.
구현 예제
다음은 위 문제를 해결하는 코드입니다.
const str = 'klmnop';
const arr = ['k', 'll', 'klp', 'klo'];
const countSubstrings = (str = '', arr = []) => {
// 각 단어가 다음으로 기대하는 문자를 기준으로 그룹화
const map = arr.reduce((acc, val, ind) => {
const c = val[0]
acc[c] = acc[c] || []
acc[c].push([ind, 0])
return acc
}, {})
let num = 0
// 원본 문자열을 한 번만 순회하며 매칭 진행
for (let i = 0; i < str.length; i++) {
if (map[str[i]] !== undefined) {
const list = map[str[i]]
map[str[i]] = undefined
list.forEach(([wordIndex, charIndex]) => {
// 마지막 문자까지 매칭되면 카운트 증가
if (charIndex === arr[wordIndex].length - 1) {
num += 1
} else {
// 다음으로 기대하는 문자 목록에 등록
const nextChar = arr[wordIndex][charIndex + 1]
map[nextChar] = map[nextChar] || []
map[nextChar].push([wordIndex, charIndex + 1])
}
})
}
}
return num
}
console.log(countSubstrings(str, arr));
실행 결과
3
코드 동작 방식
이 알고리즘의 핵심 아이디어는 다음과 같습니다.
먼저 reduce를 사용해 각 단어의 첫 번째 문자를 키로 하는 맵을 생성합니다. 맵의 값에는 해당 단어의 인덱스와 현재까지 매칭된 문자 위치(처음에는 0)를 함께 저장합니다.
그다음 원본 문자열 str을 앞에서부터 한 글자씩 순회합니다. 현재 문자를 기다리고 있는 단어들이 맵에 존재한다면, 해당 단어들을 꺼내어 처리합니다. 이때 이미 마지막 문자까지 매칭이 완료된 단어라면 결과 카운트를 1 증가시키고, 아직 남은 문자가 있다면 다음으로 기대하는 문자를 키로 하여 맵에 다시 등록합니다.
이 방식을 사용하면 원본 문자열을 단 한 번만 순회하면서 모든 단어의 부분 수열 여부를 동시에 확인할 수 있으므로, 각 단어마다 문자열 전체를 반복해서 검사하는 비효율적인 방법보다 훨씬 뛰어난 성능을 보입니다. 시간 복잡도는 대략 O(N + M)입니다(N은 원본 문자열의 길이, M은 배열에 포함된 모든 문자의 총합).