문제 개요
임의의 길이를 가진 문자열 'str'이 주어졌을 때, 입력 문자열에서 문자를 추가하거나 제거하지 않은 상태로 최대한 많은 부분 문자열이 회문(팰린드롬)이 되도록 문자들을 재배치하는 것이 이번 문제의 목표입니다. 회문 문자열이란 앞에서부터 읽어도 뒤에서부터 읽어도 완전히 동일한 문자열을 의미합니다.
입출력 시나리오
입력 − string str = "itnin"
출력 − 회문 부분 문자열의 수를 최대화하기 위해 재정렬된 문자열: iinnt
설명 − string 타입의 변수 str이 주어집니다. 입력 문자열의 문자들이 최대한 많은 회문을 형성하도록 재배치하고, 재배치가 불가능한 경우 'NOT POSSIBLE'을 반환합니다. 따라서 주어진 입력 문자열에 대한 출력은 'iinnt'입니다.
입력 − string str = "abaaaabb"
출력 − 회문 부분 문자열의 수를 최대화하기 위해 재정렬된 문자열: aaaaabbb
설명 − 위와 동일한 방식으로 문자열을 재배치합니다. 같은 문자들을 서로 붙여 배치하면 회문 부분 문자열의 개수가 극대화되므로, 주어진 입력 문자열에 대한 출력은 'aaaaabbb'입니다.
핵심 아이디어
회문 부분 문자열의 개수를 최대화하려면 같은 문자끼리 서로 인접하게 배치하는 것이 유리합니다. 예를 들어 길이가 n인 동일 문자 구간(예: 'aaaa') 내부에서 만들어지는 회문 부분 문자열의 개수는 n × (n + 1) / 2로, 문자가 흩어져 있을 때보다 훨씬 많습니다. 따라서 각 문자의 등장 횟수를 센 뒤 알파벳 순서대로 이어 붙인 정렬된 문자열을 만들면, 회문 부분 문자열의 수가 자연스럽게 최대화됩니다.
알고리즘 접근 방식
- string 타입 변수 str을 입력받고, 문자열의 길이를 계산하여 length라는 변수에 저장합니다.
- Rearr_string(str, length) 함수에 데이터를 전달합니다.
- Rearr_string(str, length) 함수 내부에서 다음 작업을 수행합니다.
- 크기가 26인 정수형 배열 arr[26]을 선언하고 0으로 초기화합니다.
- string 타입의 임시 변수 temp를 선언합니다.
- i가 0부터 length 미만까지 반복하는 FOR 루프를 시작하고, 루프 내부에서 arr[str[i] - 'a']++를 통해 각 알파벳의 빈도수를 계산합니다.
- i가 0부터 26 미만까지 반복하는 FOR 루프를 시작하고, 그 안에서 j가 0부터 arr[i] 미만까지 반복하는 내부 FOR 루프를 실행합니다. 루프 내부에서 temp = temp + (char)(97 + i)로 해당 문자를 temp에 이어 붙입니다.
- temp를 반환합니다.
- 결과를 출력합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
string Rearr_string(string str, int length){
int arr[26] = { 0 };
string temp = "";
for(int i = 0; i < length; i++){
arr[str[i] - 'a']++;
}
for(int i = 0; i < 26; i++){
for(int j = 0; j < arr[i]; j++){
temp = temp + (char)(97 + i);
}
}
return temp;
}
int main(){
string str = "itinn";
int length = str.length();
cout<<"회문 부분 문자열의 수를 최대화하는 문자열 재정렬 결과: "<<Rearr_string(str, length);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
회문 부분 문자열의 수를 최대화하는 문자열 재정렬 결과: iinnt
복잡도 분석
첫 번째 루프에서 문자열을 한 번 순회하며 빈도수를 계산하고(O(n)), 두 번째 루프에서는 각 문자를 한 번씩만 결과에 추가하므로 전체 시간 복잡도는 O(n), 추가로 사용되는 배열 공간은 고정된 크기 26이므로 공간 복잡도는 O(1)입니다. 즉, 매우 효율적인 선형 시간 알고리즘이라고 할 수 있습니다.