[python3] 1328. Break a Palindrome

풀이 일자: 22.10.10

난이도: [Medium]

분류: [String, Greedy]

문제 내용

palindromic한 문자열이 주어지면 이를 1개의 문자를 바꿔서 깨트리면 되는데 모든 경우의 수 중 사전적으로 가장 앞에 나오는 문자열을 반환하는 문제이다.

문제 해결 흐름

1. 특수 케이스를 생각해보자.

→ 문제에서 제시한 특수케이스는 한 글자를 바꾸더라도 palindromic함을 유지하는 경우인데 그 경우는 오직 문자열의 길이가 1일때만 가능하겠다.

2. 사전적으로 가장 작은 것을 내놓으면 된다면 Greedy하게 처리할 수 있지 않을까?

→ 앞에서부터 check를 해가면서 'a'가 아닌 문자를 'a'로 바꾸기만 하면 되는게 아닐까?

3. 예외 케이스가 있나?

→ 예를 들어 'aba'인 경우 'a'가 아닌 b를 'a'로 바꾸더라도 palindromic이 유지된다. 즉 현재의 위치가 length의 중심이고 앞 뒤가 대칭이라면 앞의 것을 바꾸는 것이 아니라 제일 마지막의 어떤 문자를 'b'로 바꾸면 되겠다.

 

class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        ans = ""
        length = len(palindrome)
        li = list(palindrome);
        if length != 1:
            for i in range(length):
                if (li[i] != 'a'): 
                    if li[0:i] == li[length-1:i:-1]:
                        break
                    li[i] = 'a';
                    ans = ''.join(li);
                    break;
            if ans == '':
                li[-1] = 'b';
                ans = ''.join(li);
        return ans

다른 해결 방식

대다수 나와 같은 idea를 가지고 풀어냈지만 좀더 간결하게 풀어낸 방법이 존재하였다.

1. 어차피 palindromic을 유지할거니까 반만 보고도 처리가 가능하지 않을까?

→  물론 내 코드도 'b'를 붙이는 조건이 아닌 이상 n/2부분 전에서 처리되겠지만 'b'를 더해주는 경우 반까지 확인하고 없으면 마지막에 추가하면 되기에 더 좋은 코드가 될 것이다.

class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        n = len(palindrome)
        if n == 1:
            return ''
        for i in range(n // 2):
            if palindrome[i] != 'a':
                return palindrome[:i] + 'a' + palindrome[i + 1:]
        return palindrome[:-1] + 'b'

 

문제 링크

https://leetcode.com/problems/break-a-palindrome/