문제 정의
서로 순열(permutation) 관계에 있는 n개의 문자열이 주어집니다. 우리는 '문자열의 첫 번째 문자를 맨 뒤로 옮기는' 연산을 반복하여 모든 문자열을 동일하게 만들어야 하며, 그때 필요한 최소 연산 횟수를 구하는 것이 목표입니다.
예시
배열이 arr[] = {"abcd", "cdab"}와 같이 주어졌다면, 두 문자열을 같게 만들기 위해 총 2번의 이동이 필요합니다.
- 첫 번째 문자열 "abcd"에서 문자 'a'를 맨 뒤로 이동합니다. 연산 후 문자열은 "bcda"가 됩니다.
- 이어서 문자 'b'를 맨 뒤로 이동합니다. 연산 후 문자열은 "cdab"가 되며, 이제 두 문자열이 완전히 동일해집니다.
알고리즘 접근 방식
핵심 아이디어는 간단합니다. 어떤 문자열을 기준으로 삼으면, 다른 문자열들이 그 기준 문자열과 일치하기 위해 필요한 회전 횟수를 계산할 수 있습니다. 문자열을 자기 자신과 한 번 이어 붙인 임시 문자열을 만들면, 가능한 모든 회전 형태가 그 안에 포함되므로 find 함수로 위치(회전 횟수)를 바로 찾을 수 있습니다.
- 첫 번째 문자열을 기준으로 삼습니다. 이를 str1이라고 부르겠습니다.
- str1을 자기 자신과 이어 붙여 임시 문자열을 생성합니다.
temp = str1 + str1 - 다른 모든 문자열이 현재 기준 문자열과 일치하도록 하는 데 필요한 회전 횟수를 계산합니다. temp.find()가 반환하는 인덱스가 곧 필요한 이동 횟수입니다.
- 모든 문자열을 차례대로 기준으로 삼아 위 과정을 반복하고, 그중 최솟값을 반환합니다.
만약 어떤 문자열이 기준 문자열의 회전 형태가 아니라면(즉, find 결과가 npos라면) 애초에 모든 문자열을 동일하게 만드는 것이 불가능하다는 의미입니다. 주어진 문제에서는 문자열들이 서로의 순열이며 회전으로 일치할 수 있다고 가정합니다.
구현 예제 (C++)
#include <iostream>
#include <string>
#include <algorithm>
#include <climits>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int minMoves(string str[], int n) {
int minCnt = INT_MAX;
for (int i = 0; i < n; ++i) {
int cnt = 0;
for (int j = 0; j < n; ++j) {
string temp = str[j] + str[j];
int index = temp.find(str[i]);
if (index != string::npos) {
cnt += index;
}
}
minCnt = min(cnt, minCnt);
}
return minCnt;
}
int main() {
string str[] = {"abcd", "cdab", "bacd", "cdba"};
cout << "Minimum moves: " << minMoves(str, SIZE(str)) << endl;
return 0;
}실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 출력을 얻을 수 있습니다.
Minimum moves: 2
복잡도 분석
이 알고리즘은 각 문자열을 기준으로 삼을 때마다 나머지 모든 문자열에 대해 find 연산을 수행하므로, 시간 복잡도는 O(n² × L)입니다(n은 문자열 개수, L은 문자열 길이). 문자열 개수가 많지 않은 경우에는 충분히 효율적으로 동작하지만, 입력 크기가 크다면 KMP 알고리즘 등 더 빠른 문자열 검색 기법을 적용하는 것을 고려할 수 있습니다.