길이가 모두 같은 소문자 문자열 N개로 이루어진 배열 A가 있다고 가정해 봅시다. 이제 임의의 삭제 인덱스 집합을 선택하고, 각 문자열에서 해당 인덱스에 있는 문자들을 모두 삭제할 수 있습니다.
예를 들어 배열 A가 ["abcdef", "uvwxyz"]이고 삭제 인덱스가 {0, 2, 3}이라면, 삭제 후 최종 배열은 ["bef", "vyz"]가 됩니다. 이때 A에 남은 열들은 ["b","v"], ["e","y"], ["f","z"]입니다.
삭제 인덱스 집합 D를 골랐을 때, 삭제 후 A의 모든 남은 열이 내림차순 없이(비내림차순) 정렬되어 있어야 한다고 합시다. 우리가 구해야 할 것은 이 조건을 만족하는 D 길이의 최솟값입니다.
예제로 이해하기
입력이 ["cba", "daf", "ghi"]라면 출력은 1이 됩니다. D = {1}을 선택하면 각 열인 ["c","d","g"]와 ["a","f","i"]가 비내림차순으로 정렬되기 때문입니다. 반면 D = {}처럼 아무것도 삭제하지 않으면 ["b","a","h"] 열은 정렬되어 있지 않아 조건을 만족하지 못합니다.
해결 접근 방법
이 문제는 다음 단계로 해결할 수 있습니다.
- A를 행렬로 변환합니다. 즉, 배열의 각 문자열에서 문자를 분리해 열(column) 단위로 나눕니다.
- B라는 새로운 빈 리스트를 만듭니다.
- A의 각 열 col에 대해 다음을 수행합니다.
- col이 이미 정렬되어 있다면 B에 0을 삽입합니다.
- 그렇지 않다면 B에 1을 삽입합니다.
- B의 모든 요소의 합을 반환합니다. 이 값이 삭제해야 할 최소 열 개수입니다.
핵심 아이디어는 zip(*A)를 사용하면 문자열 배열을 손쉽게 열 단위로 전치(transpose)할 수 있다는 점입니다. 그리고 sorted(col) == list(col) 비교를 통해 해당 열이 이미 정렬되어 있는지 한 번에 판별할 수 있습니다.
구현 예제
class Solution:
def minDeletionSize(self, A):
return sum([1-(sorted(col)==list(col)) for col in zip(*A)])
ob = Solution()
print(ob.minDeletionSize(["cba","daf","ghi"]))
입력
["cba","daf","ghi"]
출력
1
이 풀이의 시간 복잡도는 O(N × L log L)입니다(N은 문자열 개수, L은 문자열 길이). 각 열마다 정렬 여부를 확인하기 위해 정렬 연산을 수행하기 때문입니다. 공간 복잡도는 O(L)로, 비교를 위한 임시 리스트만 필요합니다.