파이썬으로 사전순으로 가장 작은 비회문 문자열 만들기

문자열 s가 회문(palindrome)이라고 가정해 봅시다. 우리는 단 한 글자만 변경하여 s가 더 이상 회문이 아니도록 만들어야 하며, 동시에 결과 문자열은 사전순(lexicographically)으로 가장 작아야 합니다.

예를 들어 입력이 s = "level"이라면 출력은 "aevel"이 됩니다. 첫 번째 'l'을 'a'로 바꾸면 회문이 아닌 문자열 중에서 사전순으로 가장 앞서는 결과를 얻을 수 있기 때문입니다.

접근 방법

사전순으로 가장 작은 문자열을 만들려면 가능한 한 앞쪽 위치의 문자를 'a'로 바꾸는 것이 유리합니다. 다음 단계를 따릅니다.

• i를 0부터 s의 길이 절반(정수 부분) 미만까지 반복합니다.
  • s[i]가 'a'가 아니라면:
    • s를 문자 리스트로 변환합니다.
    • s[i]를 'a'로 변경합니다.
    • 리스트의 모든 문자를 이어 붙여 반환합니다.
• 앞쪽 절반이 모두 'a'인 경우:
  • s를 문자 리스트로 변환합니다.
  • 마지막 문자를 'b'로 변경합니다.
  • 리스트의 모든 문자를 이어 붙여 반환합니다.

왜 이 방법이 동작할까?

원래 문자열이 회문이므로 s[i]와 대칭 위치인 s[길이-1-i]는 항상 같은 값입니다. 따라서 앞쪽 절반(i < 길이/2)에 있는 s[i]가 'a'가 아니라면, 이것을 'a'로 바꾸는 순간 대칭 위치의 문자와 달라져 회문이 깨집니다. 이때 바꾸는 위치가 가장 앞쪽일수록 결과 문자열이 사전순으로 작아지므로, 처음으로 'a'가 아닌 문자를 찾아 'a'로 교체하는 것이 최적입니다.

만약 앞쪽 절반이 전부 'a'라면, 마지막 문자를 'b'로 바꾸는 것이 사전순으로 가장 작은 비회문 문자열을 만드는 유일한 방법입니다. 예를 들어 "aaa"는 "aab"가 됩니다.

예제 코드

class Solution:
    def solve(self, s):
        for i in range(len(s) // 2):
            if s[i] != "a":
                s = list(s)
                s[i] = "a"
                return "".join(s)
    s = list(s)
    s[-1] = "b"
    return "".join(s)

ob = Solution()
s = "level"
print(ob.solve(s))

입력

"level"

출력

aevel

복잡도 분석

이 알고리즘은 문자열을 최대 한 번 순회하므로 시간 복잡도는 O(n)이고, 문자 리스트를 새로 만들 때 공간 복잡도 역시 O(n)입니다. 파이썬 문자열은 불변(immutable)이므로 특정 위치의 문자를 직접 수정할 수 없어 리스트로 변환한 후 처리한다는 점에 유의하세요.