문자열 리스트가 주어졌을 때, 이 문자열들을 하나의 루프(고리) 형태로 연결할 수 있습니다. 각 문자열은 연결할 때 뒤집거나 그대로 사용할 수 있습니다. 가능한 모든 루프 중에서, 루프의 임의의 지점을 잘라 일반적인 문자열로 만들었을 때 사전순(lexicographically)으로 가장 큰 문자열을 찾아야 합니다.
이 문제를 해결하려면 다음 두 단계를 거쳐야 합니다.
문제 정의
1단계: 문자열 연결 — 주어진 순서대로 모든 문자열을 하나의 루프로 연결합니다. 이때 각 문자열은 원본 그대로이거나 뒤집힌 형태일 수 있습니다.
2단계: 자르기 — 루프의 아무 위치에나 하나의 절단점을 만들어 루프를 일반 문자열로 변환합니다. 절단점의 문자부터 시작하는 문자열이 되며, 가능한 모든 일반 문자열 중 사전순으로 가장 큰 것을 찾으면 됩니다.
예시
입력이 "abc", "xyz"라면 출력은 "zyxcba"입니다. 루프 상태의 문자열은 다음과 같이 만들 수 있으며, 여기서 '-'는 루프로 연결된 상태를 나타냅니다.
- -abcxyz-
- -abczyx-
- -cbaxyz-
- -cbazyx-
정답인 "zyxcba"는 네 번째 루프에서 가운데 문자 'a'를 기준으로 잘라 얻은 결과입니다.
해결 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
solve() 함수
solve()함수는 인덱스(idx), 문자열 배열(strs), 뒤집기 여부(rev)를 매개변수로 받습니다.temp := strs[idx]로 설정하고, rev가 참이면 temp를 뒤집습니다.- 빈 문자열 str1과 str2를 준비합니다.
- i가 0부터 idx 미만일 때까지 반복하며 str1에 strs[i]를 이어 붙입니다.
- i가 idx+1부터 배열 끝까지 반복하며 str2에 strs[i]를 이어 붙입니다.
- k가 0부터 temp 길이 미만일 때까지 반복하며 다음을 수행합니다.
- newOne = temp의 k번째부터 끝까지 + str2 + str1 + temp의 처음부터 k-1번째까지
- ret이 비어 있거나 ret이 newOne보다 작으면 ret := newOne으로 갱신합니다.
findMax() 함수
- 각 문자열에 대해 원본과 뒤집은 버전을 비교하여 더 큰 쪽을 strs[i]에 저장합니다. 이렇게 하면 각 문자열이 개별적으로 최적의 방향을 갖게 됩니다.
메인 로직
- ret을 빈 문자열로 초기화합니다.
- findMax(strs)를 호출해 각 문자열의 방향을 최적화합니다.
- 모든 인덱스 i에 대해 solve(i, strs, false)와 solve(i, strs, true)를 호출합니다.
- 최종 ret을 반환합니다.
C++ 구현 예제
다음 구현을 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string ret;
void solve(int idx, vector <string > strs, bool rev){
string temp = strs[idx];
if (rev)
reverse(temp.begin(), temp.end());
string str1 = "";
string str2 = "";
for (int i = 0; i < idx; i++)
str1 += strs[i];
for (int i = idx + 1; i < strs.size(); i++)
str2 += strs[i];
for (int k = 0; k < temp.size(); k++) {
string newOne = temp.substr(k) + str2 + str1 + temp.substr(0, k);
if (ret == "" || ret < newOne) {
ret = newOne;
}
}
}
void findMax(vector<string>& strs){
for (int i = 0; i < strs.size(); i++) {
string temp = strs[i];
reverse(temp.begin(), temp.end());
strs[i] = strs[i] > temp ? strs[i] : temp;
}
}
string splitLoopedString(vector<string>& strs) {
ret = "";
findMax(strs);
for (int i = 0; i < strs.size(); i++) {
solve(i, strs, false);
solve(i, strs, true);
}
return ret;
}
};
main(){
Solution ob;
vector<string> v = {"abc", "xyz"};
cout << (ob.splitLoopedString(v));
}입력
{"abc", "xyz"}출력
zyxcba
정리
이 알고리즘의 핵심은 두 가지입니다. 첫째, 각 문자열을 개별적으로 뒤집었을 때와 비교해 더 큰 형태로 미리 최적화하면 탐색 공간을 줄일 수 있습니다. 둘째, 각 문자열이 시작점이 될 수 있는 모든 경우와 뒤집기 여부를 조합하며, 해당 문자열 내부의 모든 절단 위치를 시도함으로써 전체 루프에서 얻을 수 있는 최대 사전순 문자열을 보장할 수 있습니다.