1. 문제 소개

960. Delete Columns to Make Sorted III

2. 나의 풀이

처음에는 이전과 비슷한 방법을 사용했으나 dp를 사용했다.
시간복잡도는 $O(n^2 * m)$이다.

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        n = len(strs[0])                                     # 열(column) 개수(각 문자열 길이)
        dp = [1] * n                                         # dp[i]: 열 i를 시작(또는 포함)했을 때 만들 수 있는 최대 선택 열 길이

        for i in range(n-2, -1, -1):                         # 뒤에서 앞으로 순회(후속 열 j의 dp가 먼저 계산되도록)
            for j in range(i+1, n):                          # i보다 오른쪽에 있는 열 후보 j들 탐색
                if all(row[i] <= row[j] for row in strs):    # 모든 행에서 열 i의 문자 <= 열 j의 문자인지(열 i -> j 전이 가능 조건)
                    dp[i] = max(dp[i], 1 + dp[j])            # 전이 가능하면 LIS 유사 DP 갱신
                    print(dp)                                # 디버깅 출력(최종 제출/정리에서는 제거 권장)

        return n - max(dp)                                   # 남길 수 있는 최대 열 길이를 빼서 최소 삭제 열 수 반환

3. 다른 풀이

동일한 시간복잡도에도 break를 통해 훨씬 빠르게 풀었다.

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        n = len(strs[0])              # 열(column) 개수
        m = len(strs)                 # 행(row, 문자열) 개수
        dp = [1] * n                  # dp[i]: 열 i를 마지막으로 선택했을 때 선택 가능한 최대 열 개수

        # 열 i를 마지막으로 두는 경우를 모두 계산
        for i in range(1, n):
            for j in range(i):
                ok = True             # 열 j 뒤에 열 i를 붙일 수 있는지 여부
                # 모든 행에 대해 strs[r][j] <= strs[r][i]인지 확인
                for r in range(m):
                    if strs[r][j] > strs[r][i]:
                        ok = False    # 한 행이라도 위배되면 전이 불가
                        break
                if ok:
                    dp[i] = max(dp[i], dp[j] + 1)  # 전이 가능하면 LIS 형태로 갱신

        mx = 0
        for v in dp:                  # dp 중 최댓값 = 남길 수 있는 최대 열 개수
            mx = max(mx, v)

        return n - mx                 # 전체 열 수 - 남길 열 수 = 최소 삭제 열 수

4. 마무리

비슷한 3개의 문제를 정리하면 다음과 같은 표로 볼 수 있다.

문제	삭제 대상	목표 정렬 조건	열끼리 독립?	정석 풀이
944	열	각 열이 위→아래 비내림차순(세로 정렬)	예 (열마다 독립 판정)	각 열 검사 후 위배면 삭제 카운트
955	열	문자열 배열이 사전식 비내림차순(행들 정렬)	부분적으로만 (왼쪽 열이 비교를 “확정”시킴)	왼쪽→오른쪽 스캔 + “인접쌍 확정(fixed)” 그리디
960	열	문자열 배열이 사전식 비내림차순(행들 정렬)	아니오 (열 선택 조합 최적화)	“남길 열 최대화” DP = 열 인덱스 LIS 변형