프로그래머스 12904 가장 긴 팰린드롬 자바 풀이

난이도 : Lv. 3

풀이일 : 2411074

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

프로그래머스

---

문제

---

아이디어

• 투 포인터를 사용해 팰린드롬인지 여부를 검사하자
• 왼쪽 인덱스를 하나씩 늘려가고, 각 왼쪽 인덱스마다 오른쪽 인덱스는 제일 뒤에서부터 줄어들게 설정하자

---

풀이 코드

class Solution
{
    public int solution(String s)
    {
        int answer = 0;
		// i : 왼쪽 ~ 마지막, j : 마지막 ~ i
        for (int i = 0; i < s.length(); i++) {
            for (int j = s.length() - 1; j > i - 1; j--) {
            	// 현재 검사의 최대길이 유망성 확인
                if (j - i + 1 < answer) {
                    continue;
                }
                // 팰린드롬 여부 및 포인터
                boolean palindrome = true;
                int left = i;
                int right = j;
                while (left < right) {
                	// 포인터가 가리키는 글자가 같다면 다음 글자 확인
                    if (s.charAt(left) == s.charAt(right)) {
                        left++;
                        right--;
                    }
                    // 포인터가 가리키는 글자가 다르면 팰린드롬 변경 및 종료
                    else {
                        palindrome = false;
                        break;
                    }
                }
                // 현재가 팰린드롬이고 저장된 최댓값보다 크다면 answer 재할당
                if (palindrome && answer < j - i + 1) {
                    answer = j - i + 1;
                }
            }
        }
        return answer;
    }
}

• i는 가장 왼쪽부터 오른쪽으로 증가하며, j는 제일 오른쪽 끝부터 i까지 감소한다.
• 만약, 현재 검사하는 회문의 길이가 최댓값이 될 가능성이 없다면, 더이상 진행하지 않고 다음 반복을 수행한다.
• palindrome으로 팰린드롬인지 아닌지를 저장한다.
• left 포인터가 right보다 작은 동안, 두 포인터가 가리키는 글자를 비교한다.
• 두 포인터가 가리키는 글자가 같다면, 동시에 한 칸씩 늘리고 줄여 가운데로 모이게 한다.
• 어느순간 두 포인터가 가리키는 글자가 다르다면, 팰린드롬이 아니므로 종료한다.
• 팰린드롬이라면, answer에 저장된 것과 현재 찾은 팰린드롬 중 큰 값을 answer에 할당한다.

---

느낀점

• 자바는 파이썬에 비해서 깔끔하고 효율적으로 짜지 못하는 것 같다. 파이썬을 훨씬 오래써서 앞으로도 파이썬을 훨씬 잘할려나
• 비효율적인 방식인 것 같아서 다른 방식으로도 풀어봐야지