회문(palindrome) 문자열이 하나 주어진다고 가정해 봅시다. 정확히 한 글자를 임의의 소문자 알파벳으로 교체하여, 회문이 아닌 문자열 중 사전순으로 가장 작은 문자열을 만들어야 합니다. 교체 후 최종 문자열을 반환하며, 불가능한 경우에는 빈 문자열을 반환합니다. 예를 들어 입력이 "abccba"라면 출력은 "aaccba"가 됩니다.
접근 방법
이 문제는 그리디(greedy) 전략으로 해결할 수 있습니다. 사전순으로 가장 작은 비회문을 만들려면 다음 원칙을 따릅니다.
문자열이 사전순으로 작아지려면 앞쪽 문자를 최대한 'a'로 만들어야 합니다.
따라서 왼쪽 절반을 처음부터 스캔하면서 'a'가 아닌 첫 번째 문자를 찾아 'a'로 바꾸고 곧바로 결과를 반환합니다. 이렇게 하면 문자열이 더 작아지는 동시에 회문도 깨집니다.
모든 문자가 이미 'a'라면(예: "aaaa") 어떤 글자를 바꿔도 더 작아질 수 없으므로, 마지막 문자를 'b'로 바꾸어 회문을 깨는 것이 유일한 선택입니다.
길이가 1인 문자열은 한 글자를 바꾸더라도 여전히 회문이므로 빈 문자열을 반환합니다.
예시 살펴보기
"abccba"의 경우 왼쪽 절반에서 'a'가 아닌 첫 번째 문자는 두 번째 자리의 'b'입니다. 이를 'a'로 바꾸면 "aaccba"가 되는데, 이는 원래 문자열보다 작으면서 회문이 아니므로 정답이 됩니다.
단계별 알고리즘
문자열의 길이가 1이면 빈 문자열을 반환합니다.
i := 0, j := 문자열 길이 − 1 로 초기화합니다.
i < j 인 동안 다음을 반복합니다.
s[i]가 'a'가 아니면 s[i]를 'a'로 바꾸고 s를 반환합니다.
i를 1 증가시키고 j를 1 감소시킵니다.
루프가 종료되었다면 모든 문자가 'a'라는 의미이므로 s[s.size() − 1]을 'b'로 변경합니다.
s를 반환합니다.
C++ 구현 예제
다음 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string breakPalindrome(string s) {
if(s.size() == 1) return "";
int i = 0, j = s.size() - 1;
while(i < j){
if(s[i] != 'a'){
s[i] = 'a';
return s;
}
i++;
j--;
}
s[s.size() - 1] = 'b';
return s;
}
};
main(){
Solution ob;
cout << (ob.breakPalindrome("abccba"));
}
입력
"abccba"
출력
aaccba
복잡도 분석
시간 복잡도는 O(n)이며, 입력 문자열을 제자리에서 수정하므로 추가 공간 복잡도는 O(1)입니다.