[Leetcode][955] Delete Columns to Make Sorted II

문제 : https://leetcode.com/problems/delete-columns-to-make-sorted-ii/

---

["ax", "ay", "ba", "bb"]

를 입력값으로 예를 들어보면 

1, 2행 "ax", "ay" 는 첫번째 열 a 가 같으므로 두 번째 열 x, y는 정렬이 되어야 한다.

2, 3행 "ay", "ba" 는 첫번째 열 a, b 가 같지 않고 사전순정렬이 되어있기 때문에 두 번째 열 y, a는 정렬이 될 필요가 없다.(정렬되지 않아도 사전 순 정렬이 되기 때문에)

위 개념으로 알고리즘을 생각해본다.

A 요소 개수를 N, A[i]의 길이를 M이라 하자.

N크기만큼의 bool형 배열(ordered)을 하나 만든다.

ordered[i] = A[i-1], A[i] 는 사전순 정렬이 되어있는가.

를 저장한다.

처음에는 모두 false이다.

for(int j=0; j<M; j++){
    for(int i=1; i<N; i++){
        if(A[i-1] 문자열의 j째번째 문자가 A[i] 문자열의 j째번째 문자보다 작거나 같다면
           혹은 ordered[i]가 true라면(이미 정렬된 문자열)) 
                다음 행을 탐색한다.
        else{ // 아직 정렬되지 않은 문자열인데 j번째 문자도 정렬되지 않았다면
            해당 열은 삭제되어야 한다. 
        }
    }
}

대략적 알고리즘은 위와 같다.

A[i-1] 문자열의 j번째 문자가 A[i] 문자열의 j번째 문자보다 작거나 같은 경우는 "xa", "xb"이다. j번째 문자가 a, b라면 a, b는 정렬되어 있다고 볼 수 있다.

ordered[i]가 true라면은 "az", "by" 에서 j번째 문자가 z, y이고 이는 정렬되지 않았지만 이전 문자인 a, b가 이미 정렬되어 있으므로 이후에 나오는 문자들은 사전적 순서에 영향을 끼치지 못한다.

위 두 가지 경우에 모두 속하지 않는 경우는 "xb", "xa" 인 경우다. j번째 문자가 b, a이고 이는 정렬되지 않았는데 이전 문자인 x, x도 정렬되었다고 볼 수 없다. 문자가 같아서 정렬되긴 하였지만 이후의 문자도 사전적 순서에 영향을 끼치므로 정렬되었다고 볼 수 없다고 표현했다. -> ordered 배열에서도 같은 경우는 false이다. 왜냐하면 ordered 배열은 이후 문자를 탐색해야 하는지 판단하기 위해 만든 배열이기 때문이다.

만약 해당 열이 삭제되는 경우 ordered 배열은 변하지 않는다. 

해당 열이 삭제되지 않는 경우만 ordered 배열을 갱신해준다. true로 갱신되는 경우는 ordered[i]가 false이고 현재 탐색중인 열(j)이 이전 행(i-1)의 열보다 큰 경우다. 

시간복잡도는 O(NM).

---

소스코드 : https://gist.github.com/fpdjsns/7168903d18fc907a6be174c4319b234d