Today's Algorithm(2018-10-08)

leetcode 5

이번 문제는 'Longest Palindromic Substring'입니다. Palindromic이란 말은 앞뒤로 읽어도 똑같은 문자열(회문)을 의미합니다. 예를들어 aba, abba 등이 있겠죠. 재미있는 문제라고 생각은 했지만 도무지 방향이 잡히지 않더라구요. 그래서 해답을 참고하였습니다. 다른 사람들의 해답을 보아도 비슷한 부분들이 있었는데요. 제가 고민하던 부분과 해답에서 이를 해결한 부분 중심으로 정리하도록 하겠습니다.

먼저 해답의 소스코드는 아래와 같습니다.

class Solution {
    public String longestPalindrome(String s) {
        if(s.equals("")) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i+1);
            int len = Math.max(len1, len2);
            if (len - 1 > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    public int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }
}

 

• 회문의 시작이 하나로 시작하는 것(예를 들어 aba), 두개로 시작하는 것(예를 들어 xbbx)을 어떻게 같이 처리할 수 있을까?

  • 대부분의 해답에선 이를 처리하기 위한 메서드를 따로 구성하였고 그 매개변수로 left, right를 받을 수 있도록 구성하였습니다.
  • 그 메서드 안에 while문을 돌리면서 각 후보에 대해서 left, right을 증감시키는데 이런 부분이 left와 right를 나누어 구성하는 이유라는 것과 이 부분에 대한 필요성을 느꼈습니다.
  • 저는 문자열의 처음과 마지막 처리를 어떻게 해주면 좋을지 고민을 했었는데 단순히 반복문 조건에 L >= 0, R < s.length()만 들어가면 되어서 유용하게 배웠습니다. 인덱스 번호로써 처리를 해야하군요!!
  • 마지막 return을 할 때 -1을 해주는 이유는 while문 안에 들어가고 나서 그 다음 인덱스를 위해 증감시킨 다음이기 때문에 이를 처리하기 위함입니다
  • 만약 while문에 안들어갔을 경우엔 하나로 시작하는 건 1로 반환되지만 두개로 시작하는 건 0으로 반환됩니다. 비록 두개로 시작하는게 1이 아닌 0이지만 max에서 1로 받을 것이기 때문에 큰 영향은 없습니다.

• 최대 길이를 찾았다면 출력하기 위한 인덱스 범위는 어떻게 찾을 것인가?

  • 최대길이가 나오게 된 인덱스 번호를 알면 범위를 쉽게 찾을 수 있습니다.
  • 우선 가운데가 될 인덱스 번호와 최대 길이를 2로 나눈 수가 필요할텐데요. 최대 길이를 2로 나눌 떄 start를 알기 위해선 (최대길이 - 1)이 필요하고, end를 알기 위해선 그래로 최대길이로 사용하면 됩니다. 이와 같이 구성되는 이유는 left, right 보낼 때 두개로 시작하는 것이 i, i+1이라면 왼쪽 인덱스가 중심이 되기 때문입니다.

 

혼자의 힘으로 풀어보고 싶었는데 아쉽습니다. 이런 문자열 길이와 관련된 문제가 나오게 되면 left, right로 나누고 문자열 맨 처음과 끝에 대한 처리는 조건을 좀 더 달아 제한시킨다는 점을 배울 수 있는 좋은 기회였습니다.