[프로그래머스 Level.3] 가장 긴 팰린드롬 (연습문제) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 연습문제 > 가장 긴 팰린드롬

 

 

 

문제 설명

 

 

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

 

예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.

 

 

 

 

제한사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

 

---

 

입출력 예

s	answer
"abcdcba"	7
"abacde"	3

 

 

입출력 예 설명

 

입출력 예 #1

4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.

 

 

 

입출력 예 #2

2번째자리 'b'를 기준으로 "aba"가 팰린드롬이 되므로 3을 return합니다.

 

 

 

 

 

나의 코드

class Solution {
    public int solution(String s) {
        int answer = 1;

        // s의 길이부터 2까지 진행(얼마만큼의 길이를 확인할건지)
        for(int leng=s.length(); leng>1; leng--) { 
            
            // start지점을 0부터 leng+start가 s의 길이를 벗어나지 않는만큼까지 진행(어느 지점부터 해당 길이만큼을 확인할건지)
            for(int start=0; leng+start<=s.length(); start++) { 
                boolean check = true;
                
                // leng/2만큼 돌면서 양끝에서 해당 위치의 문자들이 같은지 확인(팰린드롬이 맞는지)
                for(int k=0; k<leng/2; k++) {  
                    if(s.charAt(start+k) != s.charAt(leng+start-1-k)) {
                        check = false;
                        break;
                    }
                }
                
                if(check) return leng;
            }
        }
        
        return answer;
    }
}

 

풀이

1. 문자의 길이가 1일 때는 무조건 뒤집어도 같은 것이므로 answer를 1로 초기화 한다.
2. 3중 for문을 이용하여 첫 번째 for문에서는 (팰린드롬이 가능한) 길이를 확인하고 두 번째 for문에서는 (팰린드롬이) 시작하는 지점을 확인하고 세 번째 for문에서는 팰린드롬이 맞는지를 확인한다.
3. 가장 긴 팰린드롬의 길이를 찾는 문제이므로 leng 길이는 가장 긴 길이인 s.length()일 때부터 2일 때까지를 확인하고 start 지점은 start지점부터 해당 leng 길이만큼을 확인했을 때 s.length()를 벗어나지 않는 지점까지 확인한다.
4. 이제 팰린드롬이 가능한지 확인하면 되는데  확인하는 길이인 leng 길이의 1/2 만큼 확인하며 start 지점부터 해당 길이만큼의 양 끝에서부터의 위치의 문자가 같은지를 확인한다.
5. 만약 다른 문자가 없다면 팰린드롬이 맞으므로 해당 leng이 가장 긴 길이의 팰린드롬이므로 해당 leng을 반환한다.