문제 이해하기
이번 글에서는 JavaScript 함수를 작성해야 합니다. 이 함수는 첫 번째이자 유일한 인수로 문자열 str을 받습니다.
함수의 목표는 이 문자열을 최대한 많은 부분으로 분할하되, 각 알파벳 문자가 최대 하나의 부분에만 나타나도록 하는 것입니다. 그리고 각 부분의 크기를 정수 배열 형태로 반환하면 됩니다.
예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.
입력
const str = "ababcbacadefegdehijhklij";
출력
const output = [9, 7, 8];
출력 설명
분할 결과는 "ababcbaca", "defegde", "hijhklij" 세 부분입니다. 이렇게 나누면 모든 문자가 자신이 속한 하나의 부분 안에만 존재하게 됩니다.
반면 "ababcbacadefegde", "hijhklij"처럼 두 부분으로 나누는 방식은 잘못된 답입니다. 'a'가 첫 번째 부분에만 있어야 하지만, 이 경우 조건은 만족하더라도 요구 사항인 최대한 많은 부분으로 나누지 못했기 때문입니다.
접근 방법: 그리디 알고리즘
이 문제는 그리디(Greedy) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 먼저 문자열을 한 번 순회하면서 각 문자가 마지막으로 등장하는 인덱스를 맵(map)에 저장합니다.
- 그다음 문자열을 처음부터 순회하며 현재 부분의 끝 지점(
end)을 추적합니다. 현재 부분 범위 내의 어떤 문자가 더 뒤에서 다시 등장한다면, 해당 문자가 모두 포함되도록end를 확장합니다. - 순회 인덱스가
end에 도달하면 하나의 부분이 완성된 것이므로, 그 크기를 결과 배열에 저장하고 다음 부분 탐색을 시작합니다.
이 방식은 시간 복잡도 O(n), 공간 복잡도 O(1)(알파벳은 최대 26개)로 매우 효율적입니다.
예제 코드
다음은 위 접근 방법을 구현한 코드입니다.
const str = "ababcbacadefegdehijhklij";
const splitStrings = (str = '') => {
const res = []
const map = {}
// 각 문자의 마지막 등장 인덱스를 저장
for (let i = 0; i < str.length; i++) {
map[str[i]] = i
}
let start = 0
while (start <= str.length - 1) {
// 현재 부분의 초기 끝 지점 설정
let end = map[str[start]]
// 범위 내 문자들의 마지막 등장 위치를 확인하며 end 확장
for (let i = start + 1; i < end; i++) {
const currentEnd = map[str[i]]
if (currentEnd > end) {
end = currentEnd
}
}
// 부분 크기 저장 후 다음 시작점으로 이동
res.push(end - start + 1)
start = end + 1
}
return res
};
console.log(splitStrings(str));실행 결과
[ 9, 7, 8 ]
코드 동작 살펴보기
입력 문자열 "ababcbacadefegdehijhklij"를 기준으로 흐름을 정리하면 다음과 같습니다.
- 'a'의 마지막 등장 위치는 인덱스 8이므로, 첫 번째 부분은 최소 인덱스 0~8까지 확장됩니다. 그 범위 안의 다른 문자들('b', 'c')도 모두 인덱스 8 이전에 마지막으로 등장하므로, 첫 번째 부분의 크기는 9가 됩니다.
- 다음 시작점은 인덱스 9('d')이며, 'd'와 'e'의 마지막 등장 위치를 고려해 두 번째 부분의 크기는 7이 됩니다.
- 마지막으로 남은 구간이 세 번째 부분이 되어 크기는 8입니다.
결과적으로 [9, 7, 8]이라는 배열이 반환되며, 이는 각 문자가 하나의 부분에만 속하면서 가능한 한 가장 많은 부분으로 나눈 결과입니다.