문제 개요
소문자로만 이루어진 문자열 S가 주어졌다고 가정해 보겠습니다. 우리의 목표는 각 문자가 최대 하나의 조각에만 등장하도록 문자열을 최대한 많은 조각으로 나누고, 각 조각의 길이를 정수 리스트 형태로 반환하는 것입니다.
예를 들어 문자열이 "ababcbacadefegdehijhklij"라면 출력은 [9, 7, 8]입니다. 문자열은 "ababcbaca", "defegde", "hijhklij" 세 부분으로 나뉘며, 모든 문자가 자신이 속한 조각 안에만 존재하기 때문입니다.
반면 "ababcbacadefegde", "hijhklij"처럼 두 조각으로 나누는 방식은 올바르지 않습니다. 'a'와 'b'가 서로 다른 조각에 걸쳐 있지는 않지만, 조각의 개수가 더 적어 최대 분할 조건을 만족하지 못하기 때문입니다.
해결 전략: 그리디(Greedy) 접근법
이 문제는 그리디 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 문자가 마지막으로 등장하는 위치를 미리 기록해 두고, 문자열을 앞에서부터 순회하면서 현재 구간이 더 이상 확장될 필요가 없는 지점(구간 내 모든 문자의 마지막 등장 위치를 포함한 지점)에서 조각을 잘라내는 것입니다.
알고리즘 단계
- 각 문자의 마지막 등장 인덱스를 저장할 맵 cnt를 정의합니다.
- i를 0부터 s.size()-1까지 순회하며 cnt[s[i]] := i로 마지막 위치를 기록합니다.
- j := 0, start := 0, i := 0으로 초기화하고, n := s.size()로 문자열 길이를 저장합니다.
- 결과를 담을 배열 ans를 정의합니다.
- i < n인 동안 다음을 반복합니다.
- j := max(j, cnt[s[i]]) — 현재 구간에 포함된 문자의 마지막 등장 위치까지 경계 j를 확장합니다.
- i == j라면 현재 조각이 완성된 것이므로 ans에 i - start + 1(조각 길이)을 삽입하고, start := i + 1로 새 조각의 시작점을 갱신합니다.
- i를 1 증가시킵니다.
- 모든 순회가 끝나면 ans를 반환합니다.
C++ 구현 예제
아래 구현을 통해 동작 방식을 더 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> partitionLabels(string s) {
map <char, int> cnt;
for(int i = 0; i < s.size(); i++)cnt[s[i]] = i;
int j = 0, start = 0;
int i = 0;
int n = s.size();
vector <int> ans;
while(i < n){
j = max(j, cnt[s[i]]);
if( i == j){
ans.push_back(i-start+ 1);
start = i + 1;
}
i++;
}
return ans;
}
};
main(){
Solution ob;
print_vector(ob.partitionLabels("ababcbacadefegdehijhklij"));
}
실행 결과 확인
입력
"ababcbacadefegdehijhklij"
출력
[9,7,8]
복잡도 분석
이 알고리즘은 문자열을 두 번만 순회하면 되므로 시간 복잡도는 O(n)입니다. 또한 맵에는 알파벳 소문자 26개에 해당하는 정보만 저장되므로 공간 복잡도는 O(1)(입력 크기와 무관한 상수 공간)로 볼 수 있습니다. 문자열이 길어져도 선형 시간 안에 빠르게 처리할 수 있는 매우 효율적인 방식입니다.