LeetCode 5 - Longest Palindromic Substring - Medium (Java)

  LeetCode도 자주 들어봤는데 한번도 해본적은 없어서 한번 풀어봤다. 일단 시간 제한이 안써있으면서 TLE(시간초과)는 뜨는게 상당히 거슬린다. 시간제한 알려주든가! 프로그래머스도 그게 좀 불만인경우가 많은데.. 그리고 남의 코드를 못본다는 점이 상당히 아쉬워서 메인 OJ(Online Judge)로는 별론 것 같다. 그래도 유명한 사이트니 간간히 생각날 때 하나씩 풀어보게 될 것 같다.

 

이렇게 그래프로 보여주는건 상당히 맘에 든다.

 

 

   처음 해보는 사이트라 여기저기 눌러보다보니 DP 태그가 붙어있는걸 봤다. 이미 태그를 봐버린 이상 태그대로 푸는건 자존심 상하기도 하고 어차피 Brute Force(이하 BF)로도 가능할 것 같아서 BF(하지만 Back Tracking을 좀 끼얹은)로 풀어봤다.

 

1.

  단순히 모든 경우를 보도록 짜게되면 다음과 같이 짜볼 수 있다. (N = 입력으로 주어진 문자열의 문자 개수 = 즉 s.length())

for (int i = 0; i < N-1; i++) {
	for (int j = i+1; j < N; j++) {
    	// verify if substring [i, j] is a palindrome or not.
    }
}

  이 경우 팰린드롬 검증에 일반적으로 O(N)이 필요하므로, 총 O(N^3) = O(1000^3) 이므로 시간내에 통과할 수 없다.

 

 

2. 

  사실 '1'과 같은건데, 팰린드롬이라는 특수성을 생각해 약간만 생각을 바꾸면 BF로 가능하다. 어차피 팰린드롬을 찾는 경우이므로 어떠한 한 문자를 기준으로 잡고 그 좌우로 동일한 문자가 어디까지 이어지나 확인하는 것으로 팰린드롬을 찾아볼 수 있다. 예를들어 babad라는 문자가 있을 경우, 정중앙의 'b'를 기준으로 팰린드롬을 찾는다면 다음과 같이 2가지를 살펴보면 가능하다.

 

2.1 우선 살펴보는 수를 기준으로 잡는다. 기본적으로 그럼 pointer가 가르키는 문자는 길이가 1인 팰린드롬이다. 그러니 현재 팰린드롬의 길이를 재는 변수(cnt라 하겠다)는, cnt=1 이다.

 

2.2 이제 pointer를 기준으로 좌우로 살펴본다. 양쪽 다 'a' 이므로 가능하다. cnt=1+2=3이 된다.

 

2.3 다음을 살펴보면 b와 d 이므로 펠린드롬으로 사용할 수 없다. 따라서 최종적으로 pointer가 정중앙의 'b'에 있을 경우 최대 팰린드롬의 길이는 3이 된다.

 

2.4 처음 pointer가 가르키고 있던 글자를 포함하지 않는 경우도 봐야 한다. 이 경우 시작 cnt=0 이다. 이건 pointer의 좌를 보던 우를 보던, 어떻게 보던 짜기 나름이다. 내 경우엔 pointer를 글자의 오른쪽에 둔다고 봤다. 'b'를 보던 pointer를 약간 이동해서 공백을 본다고 생각 하면 된다. 

 

2.5 그리고 해당 위치부터 마찬가지로 좌우로 살펴보면 된다. 예시의 경우 처음부터 팰린드롬이 아니므로 더 살펴보지 않아도 된다.

 

2.6 그럼 위의 과정을, pointer를 첫번째 문자부터 마지막문자까지 이동하며 매번 좌우로 모두 살펴보면 Brute force 알고리즘을 통해 O(N^2)의 시간만에 팰린드롬을 찾을 수 있다.

 

 

3. 

  사실 위 로직만 해도 대강 O(1000^2) 이므로 매우 빠른시간엔 끝낼 수 있다. 하지만 그래도 leetcode 첫 트라이이니, 그냥 끝내긴 좀 아쉬워서 백트래킹으로 줄일 수 있을만한 시간도 추가로 줄여봤다. 별건 아니고, 가장 긴 길이가 나올 수 있는 정중앙부터 확인해서 이미 어떠한 최대 수치가 나왔을 때, pointer를 이동 후 해당 위치에서 최대치로 나올 수 있는 팰린드롬의 길이가 이미 이전 최대 수치보다 높을 수 없다면 시도를 안해보는 단순한 백트래킹 방식이다.

 

  예를들어, 이미 이전에 나왔던 최대 팰린드롬 길이가 9이라고 해보자.

그럼 pointer를 점점 이동시켜서 x까지 왔다고 하더라도, 이미 x 뒤의 공간이 4칸 뿐이므로 최대 9까지밖에 팰린드롬이 안된다. 따라서 이미 구해진 9보다 높을 수 없으므로 진행을 해볼 필요가 없다. 

 

 

 

코드 : github

class Answer {
      int maxLen, mid;
      boolean type;

      public Answer(int maxLen, int mid, boolean type) {
          this.maxLen = maxLen;
          this.mid = mid;
          this.type = type;
      }
  }

class Solution {
    Answer answer = new Answer(1, 0, true);

    private void setMaxPalindromLen(String str, int mid) {
        int num = Math.min(mid, str.length()-mid-1);
        int cnt = 1;
        for (int i = 1; i <= num; i++) {
            if (str.charAt(mid-i) != str.charAt(mid+i)) break;
            cnt+=2;
        }
        if (answer.maxLen < cnt) answer = new Answer(cnt, mid, true);

        num = Math.min(mid+1, str.length()-mid-1);
        cnt = 0;
        for (int i = 1; i <= num; i++) {
            if (str.charAt(mid-i+1) != str.charAt(mid+i)) break;
            cnt+=2;
        }
        if (answer.maxLen < cnt) answer = new Answer(cnt, mid, false);
    }

    public String longestPalindrome(String str) {
        if (str.length() == 1)
            return str;

        for (int mid = str.length()/2; mid >= 0; mid--) {
            if ((mid+1)*2 < answer.maxLen) continue;
            setMaxPalindromLen(str, mid);
        }

        for (int mid = str.length()/2+1; mid < str.length(); mid++) {
            if ((str.length() - mid+1)*2 <= answer.maxLen) continue;
            setMaxPalindromLen(str, mid);
        }

        StringBuilder res = new StringBuilder();
        for (int i = answer.mid - answer.maxLen/2 + (answer.type?0:1); i <= answer.mid + answer.maxLen/2; i++)
            res.append(str.charAt(i));

        return res.toString();
    }
}