이 문제에서는 문자열이 제공됩니다. 우리의 임무는 현재 문자열에 가장 가깝고 인접한 중복 문자를 포함하지 않는 문자열을 인쇄하는 것입니다.
문제를 이해하기 위해 예를 들어보겠습니다.
Input: string = “good” Output: goad
이 예에서는 인덱스 1과 2의 요소가 동일하므로 인덱스 2의 요소를 변경합니다.
이 문제를 해결하기 위해 문자열을 탐색하고 인접한 두 요소가 동일한지 확인합니다. 그렇다면 두 번째 요소를 변경합니다(i와 i+1 요소가 동일하면 i+1 요소 변경). 이 문제를 풀기 위해 greedy 알고리즘이 사용되며 유사한 요소의 인접한 각 쌍에 대해 하나의 변경을 수행합니다. 한 가지 명심해야 할 것은 변경하는 동안 주변의 모든 요소를 확인하는 것입니다. 즉, i+1을 변경한 후보다 i번째 요소를 변경하는 경우 i 인덱스 요소는 달라야 합니다.
예시
솔루션 구현을 보여주는 프로그램,
#include <iostream>
#include <string.h>
using namespace std;
void printStringWithNoDuplicates(string str){
int len = str.length();
for (int i = 1; i < len; i++){
if (str[i] == str[i - 1]){
str[i] = 'a';
while (str[i] == str[i - 1] || (i + 1 < len && str[i] == str[i + 1])) str[i]++;
i++;
}
}
cout<<str;
}
int main(){
string str = "good";
cout<<"The orignal string is : "<<str<<endl;
cout<<"String without adjecent duplicate characters is : ";
printStringWithNoDuplicates(str);
return 0;
} 출력
The orignal string is : good String without adjecent duplicate characters is : goad