[LeetCode] 960. Delete Columns to Make Sorted III

https://leetcode.com/problems/delete-columns-to-make-sorted-iii/description/?envType=daily-question&envId=2025-12-22

LeetCode - Delete Columns to Make Sorted III

문제 유형: 다이나믹 프로그래밍, 문자열 처리

문제 난이도: Hard

 

문제

You are given an array of n strings strs, all of the same length.

We may choose any deletion indices, and we delete all the characters in those indices for each string.

For example, if we have strs = ["abcdef","uvwxyz"] and deletion indices {0, 2, 3}, then the final array after deletions is ["bef", "vyz"].

Suppose we chose a set of deletion indices answer such that after deletions, the final array has every string (row) in lexicographic order. (i.e., (strs[0][0] <= strs[0][1] <= ... <= strs[0][strs[0].length - 1]), and (strs[1][0] <= strs[1][1] <= ... <= strs[1][strs[1].length - 1]), and so on). Return the minimum possible value of answer.length.

 

n개의 문자열이 들어있는 배열 strs가 있다. 이 문자열들은 모두 길이가 같다.

당신은 열 단위로 제거가능하다.

각 문자열들이 모두 nondecreasing order가 되도록 하는 최소 제거횟수를 구하시오.

 

풀이

컬럼을 최소 삭제를 하면, LIS스타일의 문자열이 남는다.

문제를 바꿔보자. 컬럼을 삭제하지 않고 LIS의 최대 길이를 구하는 것으로 바꿔본다.

즉, 열 기준 LIS문제로 바꾸고, 정답은 m - LIS길이로 하면 되는것이다.

 

dp[i] = i인덱스를 마지막으로 할 때, 최대 LIS길이로 한다. 자기 자신은 항상 가능하므로, 1이 기본값이다.

i번쨰 열에 대해서, 이전 열들을 조사한다.

이제, 모든 strs의 행에 대해, strs[r][j] <= strs[r][i]인지 검사한다.

반대 경우가 생기면, 안된다.

가능한 경우가 있다면, i는 j 뒤에 붙여도 되는것이다.

즉, 각 문자열이 사전순임을 만족하기 위해서, 각 문자열에 대해 이 문자를 붙일 수 있는지를 보는 것이다.

 

이렇게 하면, dp의 최대값은 열 단위로 종합된 LIS의 길이가 나오고, 전체길이인 m에서 빼주면, 최소 삭제수가 되는것이다.

 

코드

C++

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int n = strs.size();
        int m = strs[0].size();

        vector<int> dp(m, 1);
        for(int i = 1; i < m; i++) {
            for(int j = 0; j < i; j++) {
                bool ok = true;
                for(int r = 0; r < n; r++) {
                    if(strs[r][j] > strs[r][i]) { ok = false; break;}
                }
                if(ok) dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        return m - *max_element(dp.begin(), dp.end());
    }
};