[LeetCode] 1328. Break a Palindrome

문제 출처: https://leetcode.com/problems/break-a-palindrome/

Break a Palindrome - LeetCode

---

문제

영어 소문자로 이루어진 회문 문자열 palindrome이 주어지면, 이 문자열을 회문이 아닌 문자열로 만들기 위해 정확히 한 개의 문자를 다른 영어 소문자로 대체하고, 가능한 결과 중 사전 순에서 가장 작은 문자열을 찾아라.

 

결과 문자열을 반환하라. 만약 어떤 문자를 대체하더라고 회문이 아닌 문자열을 만들지 못하는 상황이라면, 빈 문자열을 반환하라.

 

(같은 길이의) 문자열 a와 b가 있을 때, a와 b의 문자열이 달라지는 첫 문자가 a가 b의 문자에 비해 엄격히 작을 때에 a 문자열이 b 문자열보다 작다고 할 수 있다. 예를 들어, "abcc"는 "abcd"보다 더 작은데, 이 둘이 달라지는 첫 문자인 "c"와 "d"를 비교했을 때 "c"가 "d"보다 작기 때문이다.

예제

Input: palindrome = "abccba"
Output: "aaccba"

Explanation: There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba".
Of all the ways, "aaccba" is the lexicographically smallest.

Input: palindrome = "a"
Output: ""

Explanation: There is no way to replace a single character to make "a" not a palindrome, so return an empty string.

Input: palindrome = "aa"
Output: "ab"

Input: palindrome = "aba"
Output: "abb"

---

풀이

회문(팰린드롬) 문자열을 도식화하면 아래와 같다.

위 그림의 연결된 선 중에서 한 개의 선이라도 = 관계가 깨지게 되면 그 문자열은 회문이 아니게 된다. 즉, = 관계에 있는 임의의 지점을 선택하여 현재 문자가 아닌 다른 문자로 바꾸기만 하면, 회문 상태를 깰 수 있다.

 

그렇다면 사전순으로 볼 때, 가장 작은 문자를 어떻게 찾을 수 있을까.

 

우선, 단일 문자로 볼 때, 가장 작은 문자는 'a'이다. 이것을 이용하여 문자열을 앞에서부터 보다가 'a'가 아닌 문자가 = 관계에 있다면, 해당 문자를 'a'로 바꿔보자. 

 

"abccba" => "aaccba"

 

이보다 작은 문자를 만들 수 있을까? 불가능할 것이다. 왜냐하면, 문자열의 대소를 비교할 때 핵심이 두 문자열에서 처음으로 다른 문자가 나오는 지점의 문자를 비교하는 것이기 때문이다.

 

정리하자면, 'a'가 소문자 중 가장 작은 문자이기 때문에, 이 문자를 다른 문자로 바꾼다는 것은 문자의 크기를 키우는 일이다. 그렇기 때문에 'a'가 아닌 문자 중에서 가장 첫 번째 문자를 'a'로 바꾸는 것이 가장 작은 문자열을 찾을 수 있는 방법인 것이다.

var breakPalindrome = function(palindrome) {
    const N = palindrome.length;
    for (let i = 0; i < Math.floor(N/2); i++) {
    	if (palindrome[i] != 'a') {
            return palindrome.slice(0, i) + 'a' + palindrome.slice(i+1);
        }
    }
}

그렇다면, 주어진 회문이 'a'로만 이루어질 경우를 예외로 생각해볼 수 있다. 이때는 단순하게 마지막 문자를 'b'로 대체하는 것으로 해답을 찾을 수 있다.

 

'b'는 'a'보다는 큰 문자이기 때문에, 마지막 위치가 아닌 다른 위치를 선택하여 바꾸게 되면 해당 위치가 첫 번째로 달라지는 위치가 되어 더 큰 문자열로 인식될 것이기 때문에 마지막 위치를 바꾸는 것이 가장 작은 문자열을 만드는 방법이 된다.

 

추가적으로 입력으로 주어진 회문의 길이가 1인 경우에는 회문이 아닌 문자로 바꿀 수가 없기 때문에 이 케이스에 대한 예외처리를 해줘야 한다.

var breakPalindrome = function(palindrome) {
    const N = palindrome.length;
    
    if (N == 1) return '';
    
    for (let i = 0; i < Math.floor(N/2); i++) {
    	if (palindrome[i] != 'a') {
            return palindrome.slice(0, i) + 'a' + palindrome.slice(i+1);
        }
    }
    
    return palindrome.slice(0, N-1) + 'b'
}

 

Github: 1328.js

GitHub - opwe37/Algorithm-Study