[91] 코딩테스트: 가장 긴 팰린드롬 자바 풀이

코딩테스트 준비 91일차

 

오늘 풀 문제는 가장 긴 팰린드이다.

 

우선 모든 경우의 수를 탐색해야한다고 생각했고,

이분탐색을 고민하다가 for문 2개를 사용해서 풀이했다.

 

 

가장 큰 팰린드롬

• 브루트포스
  • 가능한 모든 경우의 수를 전부 탐색해서 정답을 찾는 방식
  • 문자열의 모든 부분 문자열 확인
    • for (int i = 0; i < s.length(); i++)
    • for (int j = i; j < s.length(); j++)
  • 팰린드롬체크
    • check(s, i, j)
    • 팰린드롬이면 그 길이를 저장하고 가장 긴 길이를 구함 => 정답

 

출처: 프로그래머스 가장 큰 팰린드롬 자바 풀이

 

 

프로그래머스

 

 

정답 코드

class Solution {
    public int solution(String s) {
        int max = 1; //최소값을 1임

        for (int i=0; i<s.length(); i++) { //시작점은 0부터
            for (int j=i; j<s.length(); j++) { //끝점은 i부터
                if (check(s, i, j)) {
                    max = Math.max(max, j - i + 1); //끝점-시작점+1 (4~6 = 3)
                }
            }
        }

        return max;
    }

    private boolean check(String s, int str, int end) {
        while (str <= end) { //같은 위치때까지 확인해야함
            if (s.charAt(str) != s.charAt(end)) {
                return false;
            }
            str++;
            end--;
        }
        return true;
    }
}