문제 개요
이 문제에서는 하나의 문자열이 주어지며, 우리의 과제는 현재 문자열과 가장 가까우면서(즉, 변경 횟수가 최소인) 인접한 중복 문자를 하나도 포함하지 않는 문자열을 출력하는 것입니다.
예시를 통해 문제를 이해해 보겠습니다.
입력: string = "good" 출력: goad
위 예시에서 인덱스 1과 2의 문자가 서로 같으므로('o', 'o'), 인덱스 2의 문자를 변경하여 'goad'를 얻습니다.
접근 방법
이 문제는 그리디(Greedy) 알고리즘으로 해결할 수 있습니다. 문자열을 처음부터 끝까지 순회하면서 다음 과정을 수행합니다.
- 문자열을 순회하며 인접한 두 문자가 같은지 확인합니다.
- 같다면 뒤쪽 문자(i+1 위치)를 변경합니다. 변경 시에는 왼쪽 이웃(i)과 오른쪽 이웃(i+2) 모두와 겹치지 않도록 해야 합니다.
- 각 인접 중복 쌍마다 한 번의 변경만 수행하므로 전체 변경 횟수가 최소화됩니다.
여기서 핵심은 문자를 변경할 때 양옆의 모든 이웃 문자를 함께 확인해야 한다는 점입니다. 예를 들어 i번째 문자를 바꿀 때, 변경 후에 i번째와 i+1번째 문자가 서로 달라야 할뿐만 아니라, 새로 바꾼 문자가 그 앞 문자와도 달라야 합니다.
구현 예제
위 해결 방법을 C++로 구현한 프로그램입니다.
#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<<"원본 문자열 : "<<str<<endl;
cout<<"인접 중복 문자가 제거된 문자열 : ";
printStringWithNoDuplicates(str);
return 0;
}실행 결과
원본 문자열 : good 인접 중복 문자가 제거된 문자열 : goad
동작 설명
코드의 핵심 로직을 살펴보면 다음과 같습니다.
- 인덱스 1부터 시작해 현재 문자(str[i])가 바로 앞 문자(str[i-1])와 같은지 검사합니다.
- 중복이 발견되면 해당 위치를 임시로 'a'로 설정한 뒤, 앞 문자 또는 뒤 문자와 충돌하지 않을 때까지 문자를 하나씩 증가시킵니다.
- 변경이 완료되면 해당 위치는 이미 처리되었으므로 i를 하나 더 증가시켜 건너뜁니다.
이 알고리즘은 각 위치를 한 번씩만 검사하므로 시간 복잡도는 O(n)이며, 추가 공간 없이 문자열 자체를 수정하므로 공간 복잡도는 O(1)입니다. 문자 종류가 충분히 많다면(영어 소문자 26개 등) 항상 유효한 대체 문자를 찾을 수 있습니다.