Python에서 정렬되도록 열 삭제

<시간/>

N개의 소문자 문자열 배열이 있고 배열 이름이 A이고 모든 문자열의 길이가 같다고 가정합니다. 이제 삭제 인덱스 세트를 선택할 수 있으며 각 문자열에 대해 해당 인덱스의 모든 문자를 삭제합니다.

예를 들어 ["abcdef","uvwxyz"]와 같은 배열 A가 있고 삭제 인덱스가 {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 =배열에서 문자열을 가져와 행렬을 만들고 문자를 다른 열로 분리
B =새로운 빈 목록
A의 col에 대해, do
- col이 이미 정렬된 경우 B에 0을 삽입
- 그렇지 않으면 B에 1 삽입
B에 있는 모든 요소의 합을 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

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"]