평가

문제 링크 : https://leetcode.com/problems/longest-palindromic-substring

결과 : 성공
풀이시간 :40분

문제 설명

회문을 찾는 문제다.
기러기, 우영우, 역삼역 등 문자열을 뒤집어도 똑같은 문자열이 나오는 걸 회문이라고 한다.

아이디어

두 가지 케이스로 나누어서 문제를 풀었습니다.
회문의 개수가 홀수일 때와, 짝수일 때를 나누었는데요,

홀수 상황

홀수일 때는 가운데 문자열을 기준으로 같은 거리에 있는 문자끼리 길이가 같아야 합니다.

짝수 상황

짝수일 때는 가운데 두 개의 문자열이 일치하고, 같은 거리에 있는 문자끼리 길이가 같아야 합니다.

풀이

코드는 다음과 같습니다. 시간복잡도는 n^2이 됩니다.

문자열의 각 문자를 순회합니다.
선택된 문자는 가운데 문자라고 가정하고, 회문의 양 끝 점을 찾습니다.
만약 만들어진 회문이 기존의 회문보다 길이가 길면, 현재 회문의 최대길이 max를 갱신하고 시작점과 끝점을 찾습니다.

class Solution {
    public String longestPalindrome(String s) {
        char[] strs = s.toCharArray();
        int max = 0;
        int maxStart = 0;
        int maxEnd = 1;
        Distance distance;
        
        for(int i=0; i<s.length(); i++) {
            distance = calculateOddAnswer(strs, i);
            if (distance.end - distance.start > max) {
                maxEnd = distance.end;
                maxStart = distance.start;
                max = maxEnd - maxStart;
            }
            if (i+1 < strs.length && strs[i] == strs[i+1]) {
                distance = calculateEvenAnswer(strs, i);
                if (distance.end - distance.start > max) {
                    maxEnd = distance.end;
                    maxStart = distance.start;
                    max = maxEnd - maxStart;
                }                
            }
        }
        return s.substring(maxStart, maxEnd);  
    }
    
    public Distance calculateOddAnswer(char[] strs, int idx) {
        int dist = 1;
        int start = idx;
        int end = idx + 1;
                
        while(true) {
            if (idx - dist < 0 || strs.length <= idx + dist) {
                return new Distance(start, end);
            }
            if (strs[idx - dist] == strs[idx+dist]) {
                dist++;
                start--;
                end++;                
            } else {
                return new Distance(start, end);
            }
        }
    }

    public Distance calculateEvenAnswer(char[] strs, int idx) {
        int dist = 1;
        int start = idx;
        int end = idx + 2;
        
        while(true) {
            if (idx - dist < 0 || strs.length <= idx + dist + 1) {
                return new Distance(start, end);
            }
            if (strs[idx - dist] == strs[idx+dist+1]) {
                dist++;
                start--;
                end++;
            } else {
                return new Distance(start, end);
            }
        }
    }

    static class Distance {
        int start;
        int end;

        public Distance(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}

또 다른 풀이(DP)

해당 방식으로 풀이한 블로그의 링크를 첨부하겠습니다.
https://izmirprogramming.tistory.com/12