[자바] Leetcode 1332 - Remove Palindromic Subsequences

싫어요가 좋아요보다 2배 이상 많아서 긴장했는데, 생각보다 나쁘지 않았다. 나름 발상의 전환을 필요로 해서 내 아무래도 기본다지기를 좋아하는 리트코드 유저들한테는 별로였나보다.

이 문제는 주어지는 알파벳이 a와 b뿐이라는 점이 엄청난 힌트가 되고, remove를 실시해야 하는 횟수만 구하면 된다는 점이 풀이를 간결하게 만든다. 

주어진 제한 속에서 가능한 답은 3가지 뿐이다. 

1) s가 null일 때 → return 0

2) s가 Palindrome일 때 → return 1

3) s가 Palindrome이 아닐 때 → 글자 하나를 제거해서 팰린드롬을 만들 수 있기 때문에 return 2

 

이중에서 1번과 2번은 바로 이해가 되는데, 과연 3번이 정말 모든 경우에 해당될 지가 사실 좀 의문이다. 여태 내가 만든 테스트케이스들만으로 확인했을 때는 진짜 문자 1개만 제거하면 팰린드롬을 만들 수 있기는 하던데, 수학적으로 증명하고 싶다 ㅠㅠ

class Solution {
    public int removePalindromeSub(String s) {
        
        
        if(s.length()==0 || s==null){
            return 0;
        }
        
        int a = 0;
        int b = s.length()-1;
        
        
        while(a<b){
            if(s.charAt(a)==s.charAt(b)){
                a++;
                b--;
            }else{
                return 2;
            }
        }
        
        return 1;
        
    }
}