[4월 7일] Longest Palindromic Substring (Bruth Force)

📙 1. 문제

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

Longest Palindromic Substring - LeetCode

문제 설명

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

제한 사항

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

풀이 1 : Brute Force 알고리즘

/**
 * @param {string} s
 * @return {string}
 */

const isPlaindrome = (str) => {
    const l = str.length
    let result = true;
    for(let i=0;i<l/2;i++){
        if(str[i]!==str[l-1-i]) return false;
    }
    return true;
}

var longestPalindrome = function(s) {
    let maxString = s[0];
    for(let i=2;i<=s.length;i++){ // i는 길이
        for(let j=0;j<s.length-i+1;j++){ // j는 시작 index
            if(isPlaindrome(s.substring(j,j+i))){
                maxString=s.substring(j,j+i);
            }
        }
    }
    return maxString
};

시간복잡도 = O(N^3), 공간 복잡도 = O(1)

• 길이는 2~s.length까지, 시작 index는 0~s.length-길이+1까지 모든 경우의 수를 탐색했다. 
• 각 경우마다 isPlaindrome함수를 거쳐 대칭인지 체크하여, 맞다면 maxString을 업데이트해주는 식으로 했다.
• 모든 경우의 수를 탐색해야하는, 상당히 비효율적인 코드이다. 시간복잡도는 O(n**3)이다. n(s.length)이 1000이하이기에 시간 에러는 뜨지 않았다.
• 그렇다면 어떻게 시간 복잡도를 낮출 수 있을까?
• 처음에 아래 문제처럼 hash함수를 이용할까 했으나, 이 문제는 불가능 할 것이라 생각했다. 

https://peter-coding.tistory.com/315

[4월 6일] Longest Substring Without Repeating Characters

• 누적합 알고리즘을 활용하면 될 것 같은데, 어떻게 구현해야 할 지 감이 안잡혔다.

 

풀이 2 : Two Pointer

var longestPalindrome = function(s) {
    if(s.length===1) return s;
    
    const getEven = (arr)=>{
        const index=[0,0];
        let max=1;
        
        for(let i=0; i<arr.length; i++){
            let l=i;
            let r=i+1;
            while(l>=0 && r<arr.length){
                if(arr[l]!==arr[r]) break;
                
                if(max <= r-l+1){
                    max=r-l+1;
                    index[0]=l;
                    index[1]=r;
                }
                l--;
                r++;
            }    
        }
        
        return [index,max];
    }
    
    const getOdd = (arr)=>{
        const index=[0,0];
        let max=1;
        
        for(let i=1; i<arr.length-1; i++){
            let l=i;
            let r=i;
            while(l>=0 && r<arr.length){
                if(arr[l]!==arr[r]) break;
                
                if(max <= r-l+1){
                    max=r-l+1;
                    index[0]=l;
                    index[1]=r;
                }
                l--;
                r++;
            }    
        }
        
        return [index,max];
    }
    
    const [evenIndex,evenLen] = getEven(s);
    const [oddIndex,oddLen] = getOdd(s);
    
    if(evenLen > oddLen) return s.substring(evenIndex[0],evenIndex[1]+1);
    return s.substring(oddIndex[0],oddIndex[1]+1);
};

시간복잡도 = O(N^2), 공간복잡도 = O(1)

• 짝수인 경우와, 홀수인 경우를 구분하여 풀었다. 

1. for문으로 i를 0~arr.length까지 탐색한다.
   • 여기서, 짝수는 0~arr.length-1, 홀수는 1~arr.length-2까지 탐색해주었다. 짝수일 경우, 시작점이 0이면 l=0, r=1을 탐색하기에 의미가 있다. 그러나 홀수일 경우, 시작점이 0이여도 l=0, r=0을 탐색하고 종료하기 때문에 의미가 없다. 그래서 짝수와 홀수의 i범위가 다른 것이다.
2. arr[l]과 arr[r]이 다르다면 for문을 종료한다.
3. 같다면, l--, r++를 하고 l과 r을 index배열에 저장한다 (나중에 결과값 return할 때 사용하기 위함)
4. l>=0 && r<arr.length라면 계속 반복한다.

풀이 3 : Dynamic Programming

var longestPalindrome = function(s) {
    if(s.length===1) return s;
    
    let max=1;
    let index=[0,0];
    
    const dp=[...Array(s.length)].map(r=>Array(s.length).fill(0));
    
    const getAnswer=(i,j)=>{
        max=j-i+1;
        index[0]=i;
        index[1]=j;
    }
    
    for(let i=s.length-1; i>=0; i--){
        for(let j=s.length-1; j>=i; j--){
            if(i===j){
                dp[i][j]=1;
                continue;
            }
            if(s[i]!==s[j]) continue;
            
            if(j-i===1){
                dp[i][j]=1;
                if(max<j-i+1) getAnswer(i,j);
            }
            
            if(!dp[i+1][j-1]) continue;
            dp[i][j]=1;
            
            if(max<j-i+1) getAnswer(i,j);
        }
    }
    
    return s.substring(index[0],index[1]+1);
};

시간 복잡도 : O(N^2), 공간 복잡도 : O(N^2). => 낭비되는 공간이 많다.

• i는 s.length-1~0, j는 s.length-1~i로 이중 for문을 돌려주었다.

1. i=j인 경우, 1로 채운다(최대 길이=1).
2. s[i]와 s[j]가 다를 경우, dp[i+1[j-1] === 0일 경우 continue하여 나머지 작업을 수행하지 않는다.
3. i=1,j=3(bcb)처럼 대칭인 문자열일 경우 dp[i][j]=1로 바꿔주고, 결과값이 될 index와 max를 바꿔준다.

 

 

---

🤔 2. 느낀 점

Bruth Force, DP, Two pointer 다양한 알고리즘으로 같은 문제를 풀어보았다. 시간 복잡도와 공간 복잡도가 모두 달랐고, 구현의 난이도도 달랐다. 특히 DP가 상당히 어려웠다. 다양한 알고리즘을 접해보고, 항상 시간 복잡도와 더불어 공간 복잡도도 생각해봐야겠다고 생각했다.

 

🤩 3. 한 번 더 짚고 갈 점

1. Brute Force(무차별 대입)

위의 첫 번째 풀이처럼 모든 경우의 수를 대입하여 문제를 해결하는 방식이다. 말그대로 "무식하게 다 해보는" 방식이다. 입력의계산 비용이 기하급수적으로 증가하므로 효율성 면에서는 좋지 않기에, 다른 방식 있다면 다른 방식을 권한다. 보통은 암호 해독, 패턴 인식, 데이터 마이닝 등 모든 경우의 수를 따져봐야 하는 경우 사용한다.

2. Dynammic Programming

세 번째 풀이에서 사용한 방식이다. 작은 문제의 결과를 메모이제이션하여 중복 계산을 피학, 이를 이용해 큰 문제를 해결하는 방식이다. 위 풀이의 경우, 이전 결과를 dp라는 2차원 배열에 저장하여 다음 풀이 할 때 이용하여 계산을 줄였다.

큰 부분을 작은 부분으로 쪼개며 푸는 탑 다운 방식과, 작은 부분부터 차례대로 풀어가는 바텀 업 방식이 있다. 최단 경로, 최소 비용 문제, 배낭 문제, LCS(Longest Common Subsequence)등의 문제에서 사용된다.

# 배낭 문제 : 조합 최적화 문제로, DP에서 매우 유명한 문제

 

3. Two Pointer

두 번째 풀이에서 사용한 방식으로, 두 개의 포인터를 이용해 특정 조건을 만족하는 원소를 찾는 기법이다. l과 r 두 개의 포인터를 이용해, 조건을 만족하면 l--, r++하여 연산을 이어나가는 방식으로 구현했다. 두 수의 합, 세 수의 합, 최대 부분합을 구하는 문제 등이 있다.