Lv 3. 가장 긴 펠린드롬

 

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

프로그래머스

 

 

 

 

이 문제는 주어진 문자열에서 가장 긴 팰린드롬(앞뒤가 같은 문자열)의 길이를 구하는 문제다.

모든 가능한 부분 문자열을 탐색하며,
팰린드롬인지 확인한 후 길이를 계산해 최댓값을 갱신하는 방식으로 구현했다.

solution 메서드는 문자열의 길이를 arrSize로 저장하고,
모든 가능한 시작점 i와 끝점 j를 반복문으로 탐색한다.
이때, j는 항상 i 이상부터 탐색하므로 부분 문자열의 범위를 점차 줄여가며 효율적으로 확인한다.

 

각 부분 문자열이 팰린드롬인지 확인하기 위해 isPalindrome 메서드를 호출한다.
이 메서드는 주어진 문자열의 특정 범위가 팰린드롬인지 확인하며,
시작 인덱스와 끝 인덱스에서 서로 다른 문자가 발견되면 false를 반환하고,
모든 문자가 같으면 true를 반환한다.

탐색 중 팰린드롬이 발견되고 그 길이가 기존의 최대 길이 answer보다 크면,
answer를 현재 길이로 갱신한다.
모든 탐색이 완료된 후 answer에는 가장 긴 팰린드롬의 길이가 저장되며, 이를 반환한다.
이 코드는 이중 반복문과 isPalindrome 메서드를 활용해 모든 부분 문자열을 확인하는 완전 탐색 방식을 사용하였다.

 

그리하여 효율성 부분에서 개선이 필요해 보여 타인의 코드를 참고하였다.

 

 

 

class Solution {
    private int answer = 0;

    private boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

    public int solution(String s) {
        int arrSize = s.length();

        for (int i = 0; i < arrSize; i++) {
            for (int j = arrSize - 1; j >= i; j--) { 
                if (isPalindrome(s, i, j) && (j - i + 1) > answer) {
                    answer = j - i + 1;
                }
            }
        }
        return answer;
    }
}

 

 

 

내 코드는 모든 책장을 다 뒤져서 가장 큰 책을 찾는 방법이다.
 책장의 모든 책을 전부 확인한 후 "이게 제일 크다"라고 결론을 내린다.

두 번째 코드는 가장 큰 책이 있을 법한 위치부터 찾는 방법이다.
큰 책을 찾으면 더 이상 확인하지 않고 바로 "이 책이다!"
하고 끝내 효율적인 측면에서 더욱 좋았다.

 

 

 

class Solution {
    public int solution(String s) {
        for(int i = s.length(); i > 0; i--) {
            for(int j = 0; j + i <= s.length(); j++) {
                if(isPalindrome(s, j, j + i - 1)) return i;
            }
        }
        return 0;
    }
    
    boolean isPalindrome(String value, int start, int end) {
        while(start <= end) {
            if(value.charAt(start++) != value.charAt(end--)) return false;
        }
        return true;
    }
}

# 코드출처 

https://velog.io/@jp-share/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%ACJava

[코딩테스트] 프로그래머스 - 가장 긴 팰린드롬(Java)

 

 

 

그리하여 탄생한 코드,
palindrome 인지 확인하는 부분은 로직이 같아 solution method에서
길이 기준 탐색으로 변경하고 만약 palindrome method에서 true 를 반환받으면
그 길이를 바로 반환하면서 효율성을 향상시켰다. 

 

 

 

class Solution {
    private int answer = 0;

    private boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

    public int solution(String s) {
        int arrSize = s.length();

        for (int i = arrSize; i > 0; i--) {
            for (int j = 0; j + i <= arrSize; j++) { 
                int end = j + i - 1;
                if (isPalindrome(s, j, end)) {
                    return i;
                }
            }
        }
        return 0;
    }
}