Today I Learned

오늘은 문자열 처리 관련한 문제가 약하다고 느껴져서 관련 문제를 풀어봤다.

가장 긴 팰린드롬

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

문제

주어진 단어를 뒤집어 거꾸로 읽어도 같은 단어를 팰린드롬이라고 한다. 주어진 문자열 s 내에서 가장 긴 팰린드롬의 길이를 반환하라.

풀이 과정

1. 우선 팰린드롬 여부를 판단하는 boolean 반환 메서드를 만든다.
   while문으로 투포인터 조건식을 만들어 left는 0에서 올라가고 right는 끝에서 감소하게해서 문자열 매칭 여부를 판단해 다르면 false를 바로 반환하고, 맞으면 반복문을 계속 순환한다.

2. 이중 for 문을 사용해도 효율성 바운더리 안에는 들어갈 것으로 보여 바로 이중 for문으로 i는 처음, j는 끝에서 시작해 isP 메서드를 돌린다. 이 과정에서 나오는 답안 중 가장 긴 답을 Math.max로 최대값을 뽑아 반환한다.

trouble

• 전체적인 코드 구현보다 테스트케이스 17, 18번에서 시간을 더 오래 잡아먹혔다. 알아보니 17, 18번 문제는 문자열 길이가 1이거나 아예 팰린드롬이 없는 경우일 때였다.

• 문자열이 한개면 그 한개가 팰린드롬이니 1을 반환해야 한다. 그리고 팰린드롬이 하나도 없더라도 아무 문자열 하나는 앞뒤 뒤집어도 같으니 최소한 1을 반환해야 한다. answer 를 기본값 1로 수정했더니 문제가 바로 풀렸다.

• 문자열 길이 1 같은 edge case를 항상 고려하고 문제를 풀어야 시간을 절약할 수 있다!!

Java 코드

class Solution {
    private boolean isP(int left, int right, String s){
        
        while(left<right){
            if(s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
    
    public int solution(String s) {
        int answer = 1;
        if(s.length() == 1) return 1;
        
        for(int i=0; i<s.length()-1; i++){
            for(int j=s.length()-1; j>=i; j--){
                if(isP(i,j,s)) answer = Math.max(answer, j-i+1);
            }
        }

        return answer;
    }
}