프로그래머스 Lv.3) 가장 긴 팰린드롬

가장 긴 팰린드롬

코딩테스트 연습 - 가장 긴 팰린드롬

풀이

세 가지 풀이를 시도한 문제다.

첫번째로 시도한 방법은 이분 탐색이었다. binary search로 답이 충분히 나올 수 있다고 생각했지만, 답이 홀수개라면 mid가 답보다 작은 짝수가 됐을 때 팰린드롬이 형성되지 않아서 답까지 mid가 커지지 못하는 경우가 있었다. (홀 짝 반대의 경우도) 그래서 여러가지를 고려하다가 결국 실패했고, 완전탐색을 하고자 마음먹었다.

 

두번째로 시도한 방법은 StringBuffer의 reverse 메소드를 이용하는 것이었다. 주어진 String s의 최고 길이부터 1까지 palindrome이 되는 부분을 찾아, 답을 저장하는 방법이었는데, 효율성 1번문제에서 시간초과가 떴다. 그래서 프로그래머스의 질문하기를 봤는데, 나와 같은 시간초과 문제가 있다가 palindrome 확인을 직접 구현하여 통과됐다는 글을 보았다.

 

그래서 세번째로 시도한 방법은 두번째의 로직에 StringBuffer의 reverse 대신 이분탐색할 때 만들어뒀던 palindrome 검증 메소드를 가져와 확인하는 것이었다. 결국 이 방법으로 풀어냈다.

 

생각보다 오래 걸린 문제고 IDE 없이 문제 풀기에 도전하다보니까 점점 후퇴하고 있다는 느낌이 든다.. ㅠㅠ 조금만 더 힘내자!!

 

 

코드

class Solution {
    public int solution(String s) {
        return search(s);
    }
    
    private int search(String s) {
        int answer =0;
        
        for(int i=s.length(); i>0; i--) {
            if(isPalindrome(s, i)) {
                answer = i;
                break;
            }
        }
        
        return answer;
    }
    
    private boolean isPalindrome(String s, int len) {
        boolean result = true;
        for(int i=0; i<=s.length()-len; i++) {
            int left = i;
            int right = (len-1+i);
            result = true;
            for(int steps =0; steps<(len)/2; steps++) {
                if(s.charAt(left++) != s.charAt(right--)) {
                    result = false;
                    break;
                }
            }
            if(result) {
                break;
            }
        }
        return result;
    }
}