임의의 길이를 가진 문자열 str이 주어졌을 때, 결과 문자열에서 동일한 문자가 서로 인접하여 배치되지 않도록 주어진 문자열을 재배치하는 것이 과제입니다.
입출력 시나리오 살펴보기
입력 − string str = "itinn"
출력 − 인접한 두 문자가 같지 않도록 문자열의 문자를 재배치한 결과: initn
설명 − 문자열 타입 변수 str이 주어집니다. 이제 입력 문자열의 문자들을 동일한 문자가 같은 위치에 연달아 나오지 않도록 재배치합니다. 즉, 'nn'은 서로 같고 인접해 있으므로 위치를 조정합니다. 그 결과 최종 문자열은 'initn'이 됩니다.
입력 − string str = "abbaabbaa"
출력 − 인접한 두 문자가 같지 않도록 문자열의 문자를 재배치한 결과: ababababa
설명 − 문자열 타입 변수 str이 주어집니다. 입력 문자열의 문자들을 동일한 문자가 인접하지 않도록 재배치합니다. 즉, 'bb', 'aa', 'bb', 'aa'는 각각 같은 문자가 붙어 있으므로 위치를 조정합니다. 그 결과 최종 문자열은 'ababababa'가 됩니다.
프로그램에 사용된 접근 방식
문자열 타입 변수(예: str)를 입력받고, 문자열의 크기를 계산하여 length라는 이름의 변수에 저장합니다.
length가 0인지 확인하고, 0이라면 함수를 종료합니다.
데이터를 Rearrangement(str, length) 함수에 전달합니다.
Rearrangement(arr, length) 함수 내부에서 다음을 수행합니다.
(length + 1) / 2로 문자열의 size를 설정합니다.
정수형 데이터를 저장할 vector 타입 변수 vec(26, 0)과 문자열 타입 포인터 ptr(length, ' ')를 선언합니다. 임시 정수형 변수 temp를 0으로 초기화합니다.
FOR 루프를 시작하여 str을 순회하면서, 루프 내부에서 vec[it - 'a']++로 각 문자의 빈도를 계산합니다.
문자 타입 변수 ch를 선언하고 maximum(vec) 함수 호출 결과로 설정합니다.
정수형 변수 total을 선언하고 vec[ch - 'a'] 값으로 설정합니다.
total이 size보다 큰지 확인하고, 크다면 빈 문자열을 반환합니다(재배치 불가능).
WHILE 루프를 total이 0이 될 때까지 반복하며, ptr[temp]에 ch를 저장하고 temp를 2씩 증가시키며 total을 1씩 감소시킵니다.
vec[ch - 'a']를 0으로 설정합니다. i를 0부터 26 미만까지 FOR 루프를 시작하고, 루프 내부에서 vec[i]가 0보다 큰 동안 WHILE 루프를 반복합니다. temp가 length 이상이면 1로 변경하고, ptr[temp]에 'a' + i를 저장한 뒤 temp를 2씩 증가시키고 vec[i]를 1씩 감소시킵니다.
ptr을 반환합니다.
char maximum(const vector<int>& vec) 함수 내부에서 다음을 수행합니다.
정수형 변수 high를 0으로, 문자 타입 변수 c를 선언합니다.
i를 0부터 26 미만까지 FOR 루프를 돌며, 루프 내부에서 vec[i]가 high보다 크면 high를 vec[i]로, c를 'a' + i로 설정합니다.
c를 반환합니다.
결과를 출력합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
char maximum(const vector<int>& vec){
int high = 0;
char c;
for(int i = 0; i < 26; i++){
if(vec[i] > high){
high = vec[i];
c = 'a' + i;
}
}
return c;
}
string Rearrangement(string str, int length){
int size = (length + 1) / 2;
vector<int> vec(26, 0);
string ptr(length, ' ');
int temp = 0;
for(auto it : str){
vec[it - 'a']++;
}
char ch = maximum(vec);
int total = vec[ch - 'a'];
if(total > size){
return "";
}
while(total){
ptr[temp] = ch;
temp = temp + 2;
total--;
}
vec[ch - 'a'] = 0;
for(int i = 0; i < 26; i++){
while (vec[i] > 0){
temp = (temp >= length) ? 1 : temp;
ptr[temp] = 'a' + i;
temp = temp + 2;
vec[i]--;
}
}
return ptr;
}
int main(){
string str = "itinn";
int length = str.length();
if(length == 0){
cout<<"Please enter a valid string";
}
string count = Rearrangement(str, length);
if(count == ""){
cout<<"Please enter a valid string";
}
else{
cout<<"Rearrangement of characters in a string such that no two adjacent are same is: "<<count;
}
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Rearrangement of characters in a string such that no two adjacent are same is: initn
알고리즘 핵심 정리
이 알고리즘의 핵심 아이디어는 다음과 같습니다.
먼저 각 문자의 출현 빈도를 계산합니다.
가장 많이 등장하는 문자가 전체 길이의 절반((length + 1) / 2)을 초과하면, 어떻게 배치하더라도 인접한 같은 문자를 피할 수 없으므로 재배치가 불가능합니다.
재배치가 가능하다면, 가장 빈도가 높은 문자부터 짝수 인덱스(0, 2, 4, ...)에 배치하고, 짝수 인덱스가 모두 찼을 경우 홀수 인덱스(1, 3, 5, ...)로 넘어가며 나머지 문자들을 채워 넣습니다.
이렇게 하면 같은 문자가 항상 2칸 이상 떨어져 배치되므로 인접 중복을 자연스럽게 피할 수 있습니다.
이 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도 역시 O(n)으로 매우 효율적입니다. 여기서 n은 입력 문자열의 길이입니다.