1. 문제 소개

955. Delete Columns to Make Sorted II

2. 나의 풀이

처음에는 문제를 바로 이해하지 못했다.
문제의 의미는 결국 주어진 문자열들이 사전순서로 배치되었는가, 아닌가를 체크하는 것이다.
Greedy Algorithm을 사용하여 풀었다.
시간복잡도는 $O(n * m)$이다.

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        n, m = len(strs), len(strs[0])                          # n: 문자열 개수(행), m: 문자열 길이(열 개수)
        well_sorted = [False] * (n-1)                           # well_sorted[i]: (strs[i], strs[i+1])의 순서가 이미 확정되었는지
        ans = 0                                                 # 삭제한 열 개수 누적

        for j in range(m):                                      # 왼쪽 열부터 오른쪽 열까지 순회
            not_sorted = False                                  # 현재 열 j를 삭제해야 하는지 여부

            # 1) 현재 열 j가 "삭제가 필요한 열"인지 검사
            #    - 아직 확정되지 않은 인접 쌍들만 확인한다.
            for i in range(n-1):
                if not well_sorted[i] and ord(strs[i][j]) > ord(strs[i+1][j]):  # 미확정 쌍에서 내림차순(위배) 발생
                    not_sorted = True                           # 이 열은 삭제해야 함
                    break                                       # 하나라도 위배면 즉시 종료(삭제 결정)

            if not_sorted:                                      # 삭제가 필요하다면
                ans += 1                                        # 삭제 열 개수 증가
                continue                                        # 이 열은 삭제되므로 확정 상태 업데이트 없이 다음 열로

            # 2) 삭제하지 않는 경우, 이 열에서 새롭게 "확정"되는 인접 쌍을 표시
            #    - 미확정 쌍에서 strs[i][j] < strs[i+1][j]라면, 이 열이 최초 차이점이 될 수 있으므로 순서 확정
            for i in range(n-1):
                if not well_sorted[i] and ord(strs[i][j]) < ord(strs[i+1][j]):  # 엄격히 증가하면
                    well_sorted[i] = True                        # (i, i+1) 쌍은 이제 정렬 관계가 확정됨

            # 3) 모든 인접 쌍이 확정되었으면, 이후 열은 더 볼 필요가 없다(사전식 비교에서 더 이상 영향 없음)
            if all(well_sorted):
                break

        return ans                                               # 최소 삭제 열 개수 반환

3. 다른 풀이

오늘은 넘어간다.

4. 마무리

힌트를 봤던 것이 아쉽지만 잘 풀었다.