카테고리 없음

[LeetCode] 5. Longest Palindromic Substring

컴퓨터 탐험가 찰리 2022. 1. 22. 11:50
728x90
반응형

문제

Given a string s, return the longest palindromic substring in s.

 

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

 

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.

 

 

 

2. 배운점

 

사이트에서는 단순히 brute force뿐만 아니라 다양한 접근법을 제공하고 있다. 차례대로 천천히 살펴봐야겠다.

 

접근법1, 2 ; Brute force

 

기본적인 접근법

기본적인 접근법에 대해 이야기하고 있다. palindrome의 속성상 문자열을 뒤집었을 때 기존과 공통인 substring이 있다면 정답이 된다고 1차적으로 생각할 수 있다. 그러나 설명에서는 "abacdfgdcaba"를 예로 들면서 전체 문자열의 앞 뒤 일부만 기존과 뒤집었을 때가 같은 경우에는 올바른 해답을 찾을 수 없다고 설명하고 있다.

 

 

Brute force 방법

brute force 방법으로 구한다면 O(n^3) 이나 O(n^2) + O(n)을 사용해야할 수 있다. 먼저 substring을 구한다는 것은 n개의 요소 중 2개를 선택하는 것이므로 nC2가 된다(참조 2.의 순열과 조합 링크 복습). n=1로 문자열 1개만 주어지는 경우는 예외처리를 해야한다. 어쨌든 이렇게 이중 포문을 통해 substring을 구한 후, 다시 substring을 for문을 돌면서 (i, substring.length() - i)의 일치여부를 검사해야하므로 O(n^3)이 소요된다. substring을 구하고, 검증하는 부분을 분리하면 O(n^2)을 두번 하게 된다.

 

 

 

접근법 3. Dynamic Programming

 

Dynamic Programming 이란

Dynamic Programming 이란 큰 문제를 가장 최소 단위로 쪼개서 해결한 후, 하나씩 증가시켜가면서 원래의 문제를 해결해나가는 방식이다(참조3). 참조3에서는 예시로 피보나치 수열을 들고 있다.

Fib(n) = Fib(n-1) + Fib(n-2), for n > 1

 

Dynamic Programming에는 Top-down 방식과 bottom-up 방식이 있다. Top-down 방식의 예제를 살펴보자.

 

@Test
void test() {
    Fibonacci fib = new Fibonacci();
    System.out.println("5th Fibonacci is ---> " + fib.CalculateFibonacci(5));
    System.out.println("6th Fibonacci is ---> " + fib.CalculateFibonacci(6));
    System.out.println("7th Fibonacci is ---> " + fib.CalculateFibonacci(7));
}

class Fibonacci {

    public int CalculateFibonacci(int n) {
        int memoize[] = new int[n+1];
        return CalculateFibonacciRecursive(memoize, n);
    }

    public int CalculateFibonacciRecursive(int[] memoize, int n) {
        if(n < 2)
            return n;

        // if we have already solved this subproblem, simply return the result from the cache
        if(memoize[n] != 0)
            return memoize[n];

        memoize[n] = CalculateFibonacciRecursive(memoize, n-1) + CalculateFibonacciRecursive(memoize, n-2);
        return memoize[n];
    }
}

맨 아래에서 두번째 줄에보면, memoize[n]이 반복적으로 실행되는 것을 알 수 있다. n=5를 시작으로, 계속해서 n이 감소하며 결과를 순환적으로 도출해낸다. n=2인 Base가 되는 경우를 생각해보자. CalculateFibonacciRecursive(2) = CalculateFibonacciRecursive(1) + CalculateFibonacciRecursive(0) 이므로 첫 if문에 걸려서 memoize[2] = 0 + 1 = 1이 될 것이다. 그리고 CalculateFibonacciRecursive(3) = CalculateFibonacciRecursive(2) + CalculateFibonacciRecursive(1)일텐데, CalculateFibonacciRecursive(1)은 return n 구문에 의해서 1이 반환되지만, CalculateFibonacciRecursive(2)는 아래 if문에 걸려서 memoize[n]을 반환하는 방식으로 1을 반환할 것이다.

 

이렇게 memoize라는 배열을 만들어놓고, 작은 문제의 결과를 배열에 저장하고 그것을 활용하여 다음번의 결과를 구할 때 활용할 수 있다는 것도 기억하자.

 

Botton-up 방식도 이와 유사하게 해결할 수 있다. 어쨌든 이런 방식이 DP 방식이라는 것을 이해하자.

 

 

해법

 

bottom-up 방식으로 base 케이스를 선정하고 하나씩 늘려가는 방식을 채택한다. 처음에 if문으로 s가 null이거나 빈 문자열인 경우를 처리해준다. 그리고 dp라는 2차원 배열을 초기화하는데, 2차원 배열 자체가 의미가 있다기 보다는 dynamic programming을 하기 위한 수단으로만 쓰인다.

class Solution {
    public String longestPalindrome(String s) {

        if (s == null || "".equals(s)) {
            return s;
        }
        
        int len = s.length();

        String ans = "";
        int max = 0;

        boolean[][] dp = new boolean[len][len];

        for (int j = 0; j < len; j++) {
            
            for (int i = 0; i <= j; i++) {
                
                boolean judge = s.charAt(i) == s.charAt(j);
                
                dp[i][j] = j - i > 2 ? dp[i + 1][j - 1] && judge : judge;

                if (dp[i][j] && j - i + 1 > max) {
                    max = j - i + 1;
                    ans = s.substring(i, j + 1);
                }
            }
        }
        return ans;
    }
}

 

for문 내부에서 palindromic을 판단하는 base와 증가하는 경우의 수를 만든다. j 위치로부터 i를 하나씩 늘려나가면서 i와 j 위치의 문자열이 같은지를 judge 값으로 저장하고, 

 

dp[i][j] = j - i > 2 ? dp[i+1][j-1] && judge : judge ;

 

구문을 통해서 bottom-up 방식을 적용한다. 풀어 쓰자면 i와 j의 차이가 2보다 작을때는, 예를 들어 dp[0][0]의 값은 judge로 저장되는데, 윗 줄에서 i와 j위치에 해당하는 문자열이 같은 경우에는 true로 저장했었다. 즉 j - i가 2보다 작은 경우들을 base로 하여 dp[i+1][j-1]이 palindromic인지 전체 문자열의 양 끝에서 하나씩 줄여가며 비교하는 것이다.

 

이 방법은 O(n^2)의 시간 복잡도와 O(n^2)의 공간복잡도를 갖는다.

3. 풀이

 

문자열 s 중 중간의 위치에 i번째 인덱스가 2개 위치한 것을 상상해보자. expandAroundCenter 메서드는 해당 위치부터 2개 인덱스의 문자열이 완전히 같다면 1개 인덱스에서는 --, 1개 인덱스에서는 ++를 적용하여 하나씩 인덱스를 늘려가는 방식을 사용한다. 이렇게 palindromic을 검사하면서 expand한다.

 

해답 ; approach 4

 

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) 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 > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private 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;
}

 

len1, len2는 인자로 각각 (s, i, i), (s, i, i+1)을 받아서 expandAroundCenter 메서드의 두 인덱스가 같은 위치에서 시작할 지, 한칸 떨어진 채로 시작할지를 결정하고, 그 중 길이가 긴 항목을 채택하기 위해 사용한다.

 

마지막에 start와 end를 다시 지정하는 부분이 있는데, 이것은 expandAroundCenter 메서드가 i 인덱스를 string의 중앙에서부터 확장해나가는 방식이므로, center가 되는 i에서 총 길이의 절반만큼 빼고, 더해서 start와 end 인덱스를 구하는 방식이다.

 

시간 복잡도는 O(n^2), 공간복잡도는 O(2n-1) = O(n) (constant)이다. 시간 복잡도는 for문을 돌면서 expandAroundCenter 메서드의 while문을 돌기 때문에 이와 같은 결과가 나왔다. 공간복잡도는 len1, len2의 값을 저장하고 있어야 하는데 각각 정확하게는 n/2, n/2 -1의 공간복잡도를 갖는다.  예를 들어 s의 길이가 n=5인 경우, len1 = 3, len2 = 2가 된다. 어쨌든 상수값이기 때문에 그냥 n, n-1로 봐서, 더하면 2n-1의 공간복잡도이다(어짜피 O(n) 이랑 다를게 없음). 

 

 

 

참조

 

https://leetcode.com/problems/longest-palindromic-substring/

 

 

2. 순열과 조합 원리 설명

https://m.blog.naver.com/sbssbi69/220060435293

 

 

3. educative.io , What is Dynamic Programming

https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews/m2G1pAq0OO0

 

 

728x90
반응형