문제 개요
이 문제에서는 하나의 문자열과 정수 M이 주어집니다. 우리의 목표는 이 문자열로 만들 수 있는 길이가 M인 모든 고유한 원형 문자열(circular string)을 사전순(알파벳 순서)으로 출력하는 것입니다.
예시를 통해 문제를 자세히 살펴보겠습니다.
입력: str = "ssssn", M = 3 출력: nss sns ssn sss
설명: 문자열 "ssssn"을 원형으로 이어 붙였을 때 만들 수 있는 길이 3의 부분 문자열은 sss, sss, ssn, sns, nss 입니다. 여기서 중복을 제거한 뒤 사전순으로 정렬하면 nss, sns, ssn, sss가 됩니다.
해결 접근 방법
이 문제는 다음 단계를 거쳐 해결할 수 있습니다.
- 원래 문자열을 자기 자신 뒤에 한 번 더 이어 붙여, 원형 구조를 일반적인 선형 문자열처럼 다룰 수 있게 만듭니다.
- 변환된 문자열의 각 시작 위치에서 길이 M인 부분 문자열을 모두 생성합니다.
- 생성된 문자열들을
std::set에 저장합니다. set은 중복된 값을 자동으로 제거하며, 요소를 항상 사전순으로 정렬된 상태로 유지합니다. - set의 첫 번째 요소부터 마지막 요소까지 차례대로 출력합니다.
이 알고리즘의 시간 복잡도는 각 부분 문자열을 추출하는 비용 때문에 O(N×M)입니다. 여기서 N은 문자열의 길이, M은 부분 문자열의 길이를 의미합니다.
구현 예제
다음 코드는 위에서 설명한 해결 방법의 실제 구현입니다.
#include <bits/stdc++.h>
using namespace std;
void printCircularString(string s, int l, int m) {
set<string> circularString;
s = s + s;
for (int i = 0; i < l; i++) {
circularString.insert(s.substr(i, m));
}
while (!circularString.empty()) {
cout<<*circularString.begin()<<"\t";
circularString.erase(circularString.begin());
}
}
int main() {
string str = "ssssn";
int N = str.length();
int M = 3;
cout<<"All circular strings of length "<<M<<" from the string '"<<str<<"' are:\n";
printCircularString(str, N, M);
return 0;
}실행 결과
All circular strings of length 3 from the string 'ssssn' are − nss sns ssn sss
정리
문자열을 두 배로 늘려 원형 구조를 처리하는 기법과, std::set의 자동 정렬 및 중복 제거 특성을 활용하면 별도의 정렬 과정 없이도 사전순으로 정렬된 고유한 원형 문자열을 손쉽게 얻을 수 있습니다. 코드가 간결하고 직관적이라는 장점이 있으며, 시간 복잡도는 O(N×M)으로 효율적입니다.