문제 설명
소문자로만 구성된 길이 n의 문자열 S가 주어졌을 때, 다음 조건을 모두 만족하는 두 개의 비어 있지 않은 부분 문자열 P와 Q를 찾아야 합니다.
P와 Q는 모두 S의 부분 수열(subsequence)이어야 합니다.
각 인덱스 i에 대해 S[i]는 P와 Q 중 정확히 하나에만 속해야 합니다.
P는 사전순(lexicographically)으로 가능한 한 가장 작아야 합니다.
예를 들어 입력이 S = "thelightsaber"라고 한다면, 출력은 a, thelightsber가 됩니다. 문자열 전체에서 사전순으로 가장 작은 문자인 'a'를 하나 분리해 내고, 나머지 문자들이 Q에 해당하기 때문입니다.
해결 접근 방법
이 문제는 매우 간단한 아이디어로 해결할 수 있습니다. 문자열을 정렬하면 첫 번째 문자가 곧 사전순으로 가장 작은 문자가 되므로, 그 문자를 원래 문자열에서 찾아 제거한 뒤 출력하면 됩니다. 구체적인 단계는 다음과 같습니다.
- 문자열 S를 복사하여 c를 만듭니다.
- c를 오름차순으로 정렬합니다.
- S에서 c[0](가장 작은 문자)이 처음 등장하는 위치 a를 찾습니다.
- S에서 해당 위치의 문자를 삭제합니다.
- c[0]과 남은 문자열 S를 출력합니다.
C++ 구현 예제
다음 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
void solve(string S){
string c = S;
sort(c.begin(), c.end());
int a = S.find(c[0]);
S.erase(S.begin() + a);
cout << c[0] << ", " << S << endl;
}
int main(){
string S = "thelightsaber";
solve(S);
}
입력
"thelightsaber"
출력
a, thelightsber
코드 설명
위 코드에서 solve() 함수는 먼저 입력 문자열을 복사한 뒤 정렬하여 가장 작은 문자를 확인합니다. 이후 find()로 원본 문자열에서 해당 문자의 위치를 찾고, erase()로 그 문자를 제거합니다. 마지막으로 분리된 문자와 나머지 문자열을 출력합니다. 시간 복잡도는 정렬에 의해 O(n log n)이며, 공간 복잡도는 문자열 복사를 위해 O(n)입니다.