[JAVA] 프로그래머스 가장긴 팰린드롬_브루트포스

 

문제 : 

https://school.programmers.co.kr/learn/courses/30/lessons/12904

프로그래머스

 

접근 1:

 

  - 길이를 기준으로 입력값의 길이값 부터 1이 될 때까지, 해당 길이의 팰린드롬 문자열이 있는지 확인한다.

 

  - 만약 팰린드롬 문자열을 발견하면 해당값을 출력한다.

 

 

 

 

코드 구현 : 

 

class Solution {

    private boolean recFunc(String s, int target){
        if(target == 1) return true;
        int half_len = target/2;
        int c = target%2 == 0 ? -1 : 0;
        boolean res = false;

        for(int i = 0 ; i+target <= s.length() ; i++){
            for(int j = 1 ; j <= half_len; j++){
                if(s.charAt(i + half_len - j) != s.charAt(i + half_len + j + c)) {
                    res = false;
                    break;
                }
                res = true;
            }
            if(res) break;
        }
        return res;
    }
    public int solution(String s)
    {
        int answer = s.length();
        while(!recFunc(s, answer)){
            answer--;
        }
        return answer;
    }
}

 

 

위의 방법은 시간 복잡도가 O(n^3) 으로 효율성 테스트를 통과했지만 개선이 필요하다.

 

 

 

접근 2:

 

  - 중심 idx를 0 에서부터 입력 문자열 크기까지 진행하면서 팰린드롬 문자열인지 확인한다.

 

  - 만약 팰린드롬 문자열을 발견하면 해당값과 이전의 결과값을 비교하여 결과값 보다 크면 값을 갱신한다.

 

 

위의 방법은 시간 복잡도가 O(n^2) 으로 효율성 테스트 케이스 중 최악의 경우 접근 1의 실행시간의 절반이 걸린다.

 ( 접근 1 최대 소요 시간 : 30 ms  -> 접근 2 최대 소요시간 : 15 ms )

 

 

 

 

코드 구현 : 

 

class Solution {
    public int solution(String s) {
        int maxLength = 1;
        
        for (int center = 0; center < s.length(); center++) {
            maxLength = Math.max(maxLength, expandAroundCenter(s, center, center));
            maxLength = Math.max(maxLength, expandAroundCenter(s, center, center + 1));
        }

        return maxLength;
    }

    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}