[프로그래머스/java] 가장 긴 팰린드롬

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/12904

🌱 문제

🌱 풀이

• 시도한 풀이 방법
  • 가능한 팰린드롬의 길이는 1부터 s.length() 이므로 각각의 길이에 대한 문자열을 찾아내서 , 그것이 팰린드롬이 맞는지 확인하는 방식으로 시도하였다.
  • 수행시간을 줄이고자, 가장 긴 길이부터 시작하여 팰린드롬인것이 확인되면 정답을 리턴하고 함수를 끝내도록 하였다.

첫번째 시도한 방법

• 각각의 가능한 String에 대해 문자 비교로 팰린드롬인지 확인하기
• 0번째와 n-1번째 문자 비교, 1번째와 n-2번째 문자 비교 ,,, 반복하여 확인

→ 효율성 1번 시간초과

import java.lang.StringBuilder;
class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        int n= s.length();
        String temp="";
        StringBuilder sb;
        
        loop:
        for(int i=n; i>=1; i--){ //i: 펠린드롬 길이 
            for(int j=0; j<=n-i; j++){ // 문자열 s에서 길이가 i인 경우 전부 확인 
                temp = s.substring(j,j+i);
                if(isPalindrome(temp)){ // 팰린드롬이면 answer에 해당 문자열 길이로 설정하고 반복문 종료하여 함수 끝내기
                    answer=temp.length();
                    break loop;
                }
            }
               
        }
        return answer;
    }
    
    public boolean isPalindrome(String s){ // 팰린드롬인지 확인하는 함수 
        int len=s.length();
        for(int i=0; i<len/2; i++){ // 양 끝의 문자열 비교
            if(s.charAt(i)!=s.charAt(len-1-i)) // 하나라도 같지 않으면 false 리턴
                return false;
        }
        return true;
    }
}

두번째 시도한 방법

• 첫번째 시도한 방법에서 팰린드롬인지 확인하는 부분을 함수로 따로 빼서 시간초과가 났나 해서 따로 빼지 않고 reverse함수를 이용해 main문에서 확인해보았다.
• 그냥 String에는 reverse 함수가 없어서 StringBuilder의 reverse()함수 이용하였다.
  

→ 그러나 또 효율성 1번 시간초과

import java.lang.StringBuilder;
class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        int n= s.length();
        String temp="";
        StringBuilder sb;
        
        loop:
        for(int i=n; i>=1; i--){ //펠린드롬 길이 
            for(int j=0; j<=n-i; j++){
                temp = s.substring(j,j+i);
                sb= new StringBuilder(temp);
                if(temp.equals(sb.reverse().toString())){
                    answer=temp.length();
                    break loop;
                }
            }
               
        }
        return answer;
    }
   
}

세번째 시도한 방법

• 무엇때문에 효율성 1번이 시간초과가 나는지 모르겠어서 [질문하기]와 구글링을 참고하였다.
• substring 함수의 수행시간이 O(N)이므로 이 부분에서 시간초과가 발생하는 듯 했다.
• 그래서 이 함수를 쓰지않고 그냥 s.charAt() 함수만을 이용해서 start, end 인덱스를 이용하여 문자를 비교하였다.
  → 효율성 통과

class Solution
{
    public int solution(String s)
    {
        int answer =0;
        int n= s.length();
        
        loop:
        for(int i=n; i>=1; i--){ //i: 펠린드롬 길이. 가장 긴 길이부터 살펴보기
            for(int j=0; j<=n-i; j++){
               boolean flag= true;
               int st=j; //시작 인덱스 
               int en=j+i-1; // 끝 인덱스 
               
               while(st<en){ 
                   if(s.charAt(st)!=s.charAt(en)){
                       flag=false;
                       break;
                   }
                   st++;
                   en--;
               }
               if(flag){ // 팰린드롬이면 정답 갱신하고 반복문 중단하기 
                   answer=i;
                   break loop;
               }
            }
               
        }
        return answer;
    }
   
}

🌱 최종 정답 코드

class Solution
{
    public int solution(String s)
    {
        int answer =0;
        int n= s.length();
        
        loop:
        for(int i=n; i>=1; i--){ //i: 펠린드롬 길이. 가장 긴 길이부터 살펴보기
            for(int j=0; j<=n-i; j++){
               boolean flag= true;
               int st=j; //시작 인덱스 
               int en=j+i-1; // 끝 인덱스 
               
               while(st<en){ 
                   if(s.charAt(st)!=s.charAt(en)){
                       flag=false;
                       break;
                   }
                   st++;
                   en--;
               }
               if(flag){ // 팰린드롬이면 정답 갱신하고 반복문 중단하기 
                   answer=i;
                   break loop;
               }
            }
               
        }
        return answer;
    }
   
}