[Programmers] 가장 긴 팰린드롬 - Java

문제

프로그래머스

 

풀이

처음에 2중 for문을 사용해 substring 메소드를 이용해 모든 부분 문자열을 HashSet에 저장하고, 펠린드롬인 문자열들을 확인해서 최대 길이를 계산하려고 했으나, 효율성 테스트에서 통과되지 않았다.

 

부분문자열이 약 600만개가 나올 수 있다. 이것은 메모리 입장에서는 한문자를 저장한다고 해도

6 000 000 =>  6MB가 나오게 된다. 그리고 모든 부분 문자열에 대해 StringBuilder 객체를 만드는 것도 메모리가 많이 먹게 된다.

 

메모리를 많이 먹지 않으면서, 효율적으로 탐색하는 방법은

1. 문자열 길이가 긴 부분 문자열부터 생각한다.

2. 문자열 길이에 해당하는 부분 문자열을 추출할 수 있는 인덱스(i)부터 모두 다 투포인터를 이용해서 검증해본다.

=> 여기서 생각을 잘해봐야하는게, 이중 for문이라고 하더라도, N 제곱 연산이 아니다.

2500이면 내부에서 1번만 수행하고, 

2499이면 내부에서 2번만 수행한다.(이중 fo문 curLen, i 조건 확인)

3. 펠린드롬이 최초에 나오는 길이가 문자열의 최대 길이이다.

 

시간 복잡도: O(2500 * 2500)

 

소스코드

class Solution {
    public int solution(String s) {
        int length = s.length();
        
        char[] arr = s.toCharArray();
        
        int answer = -1;
        
        for (int curLen = length; curLen >= 1; curLen--) {
            if (curLen < answer) {
                break;
            }
            
            for (int i = 0; i <= length - curLen; i++) {
                int start = i;
                int end = i + curLen - 1;
                
                boolean isPalin = true;
                
                while (start <= end) {
                    if (arr[start] != arr[end]) {
                        isPalin = false;
                        break;
                    }
                    
                    start += 1;
                    end -= 1;
                }

                if (isPalin) {
                    answer = curLen;
                    break;
                }
            }
        }
        
        return answer;
    }
}