1. 문제 소개

944. Delete Columns to Make Sorted

2. 나의 풀이

첫 시도에서는 grid로 만들어 풀었고, 필요없는 집합도 사용해 속도가 좋지 않았다.
이 경우 시간복잡도는 $O(n * m)$이다.

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        ans = 0                                         # 삭제해야 하는 열 개수 누적
        n, m = len(strs), len(strs[0])                  # n: 문자열 개수(행), m: 문자열 길이(열 개수)
        grid = [[ord(ch) for ch in s] for s in strs]    # 문자를 아스키(유니코드) 정수로 변환해 2D 배열로 저장

        for j in range(m):                              # 각 열 j에 대해 검사
            # (i+1행의 값 - i행의 값 >= 0) 여부를 i=0..n-2에 대해 계산한 불리언들을 set으로 모음
            # True만 있으면 "모든 쌍이 비내림차순", False가 하나라도 있으면 "정렬 위반 존재"
            temp = set(grid[i+1][j] - grid[i][j] >= 0 for i in range(n-1))

            if len(temp) == 2:                          # {True, False} 두 값이 모두 존재 -> 정렬 위반(False) 존재
                ans += 1                                # 해당 열 삭제
            elif not temp.pop():                        # set에 값이 하나뿐인데 그 값이 False인 경우 -> 전부 위반(적어도 한 쌍이 음수)
                ans += 1                                # 해당 열 삭제

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

3. 다른 풀이

공간복잡도도 줄이고 시간복잡도($O(n * m)$)도 조기 종료를 통해 줄인 깔끔한 푸링이다.

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        ans = 0  # 삭제해야 하는 열(column)의 개수를 누적해서 저장

        # 각 열(col)을 기준으로 검사
        for col in range(len(strs[0])):          # 문자열 길이만큼 반복 (열 단위)
            # 위에서 아래로 인접한 행(row) 비교
            for row in range(1, len(strs)):      # 두 번째 문자열부터 마지막까지
                # 현재 행의 문자 < 바로 위 행의 문자이면
                # 해당 열은 사전순(비내림차순)을 만족하지 못함
                if strs[row][col] < strs[row - 1][col]:
                    ans += 1                     # 이 열을 삭제해야 하므로 카운트 증가
                    break                        # 해당 열은 더 볼 필요 없음 (다음 열로 이동)

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

다음과 같은 한 줄짜리 풀이도 있다.

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        return sum(col!=sorted(col) for col in map(list,zip(*strs)))

4. 마무리

처음에 문제를 잘못 읽어서 쓸데없이 복잡하게 푼 것이 아쉽다.