[Leetcode 2370번 문제] 2370. Longest Ideal Subsequence

문제 설명

Ideal Subsequence란 Subsequence의 인접한 두 칸의 요소들의 인덱스 차이가 k 이내일 때를 의미한다. 어떤 문자열이 주어졌을때 그 문자열의 longest ideal string을 찾아야한다. 

입력

행렬의 길이 최대 10만, 칸 차이 최대 25

각 행렬의 요소는 a ~ z

출력

Integer , 가장 긴 Subsequence의 길이

과정

이상적인이란말을 보면 가장긴 증가하는 부분수열이 생각난다. 다만 거긴 방향인데 여긴 아니란거 그래서 이 점이 다르다

• 증가하는 부분수열에선 각 인덱스들이 왼쪽은 자기보다 작고 오른쪽은 자기보다 크거나 같은 자리를 찾아서 공통으로 사용함으로써 n^2 을 피할 수 있었는데 여기서는 그게 안된다.
• 그러면 그냥 n ^ 2을 해야하는데 그것도 잘 안된다. 일단 길이가 10만, 무조건 시간초과나는 각이다
• 앞뒤 dp로 하기, 2차원 리스트에서 벗어나면 시간초과는 안당하지만 여전히 중간에 데아터가 손실되는 문제가있다

비록 정렬하는 방식으로는 문제를 풀 수 없을 것 같지만 여전히 다른 dp 방식으로는 문제 풀 수 있을 것 같았다. 

이렇게 막힐때는 문제를 작은 부분으로 보면서 어떤 것들이 필요한지를 생각해봐야한다.

현재 내 최대 ideal 행렬 길이를 안다면 내 다음인덱스들에게

여러가지 1차원 행렬로 할 수 있지 않을까 ?

 

ith 인덱스의 요소가 ideal subsequence값을 결정하는데 필요한건 무엇인가? 

 

부분행렬이라하면 인접할 필요가 없기때문에 보통 ith에 영향을 주는건 0부터 i - 1th 인덱스의 요소들이다.

그런데 조금 생각해보면 

 

만약 내가 현재 e고 6칸뒤의 f에게 내 영향력을 행사하려고하는데.

마침 내 3칸 뒤에 e가 또있다면 내가 이 f에게 영향력을 주는게 맞는건가?

 

그리고 4칸뒤에 f가 있는데 6칸뒤에 또 f에게 영향을 주는게 맞나? 이것도 아니고. 즉 이건 냅색이다.

지금 내칸이 e라면 이전 e에서 k만큼 떨어진놈들의 최대값에서 값을 더해서 저장하면됨.

저장해야하는 값은 즉 i - k번째 요소가 아니라 a - z 들로 끝나는 단어의 dp길이이고 이중에서 i 번째 요소와 k 만큼의 차이가 있는 놈들에게서만 이 값을 가져오면 되는 것이었다. 

알고리즘 개요도

알고리즘

 

class Solution {
    int dp[26] = {0};
public:
    int longestIdealString(string s, int k) {
        int ans = 0;
        for (char c : s)
        {
            int maxVal = 1;
            for (int idx = max(c - 'a' - k, 0); idx <= min(c - 'a' + k, 25); idx++ )
            {
                maxVal = max(maxVal, dp[idx] + 1);
            }
            dp[c - 'a'] = maxVal;
        }
        for (int i = 0; i < 26; i++)
        {
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};