Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 '정렬된 상태를 만들기 위한 열 삭제 III' 알고리즘 문제

문제 개요

소문자로만 구성되고 길이가 모두 같은 N개의 문자열로 이루어진 배열 A가 주어졌다고 가정해 봅시다. 이제 임의의 삭제 인덱스 집합 D를 선택하여, 각 문자열에서 해당 인덱스에 위치한 모든 문자를 제거합니다. 삭제가 완료된 후 최종 배열의 모든 요소가 사전순(lexicographic)으로 정렬된 상태가 되도록 하는 것이 목표입니다.

조금 더 명확하게 설명하면, A[0]은 스스로 오름차순이어야 하고(A[0][0] <= A[0][1] <= ... <= A[0][n-1]), A[1] 역시 A[1][0] <= A[1][1] <= ... <= A[1][n-1]을 만족해야 합니다(여기서 n은 각 문자열의 길이입니다). 우리가 구해야 하는 값은 이 조건을 충족시키는 집합 D의 크기의 최솟값입니다.

예를 들어 입력이 ["cbcdb", "ccbxc"]라면 출력은 3이 됩니다.

해결 전략

이 문제는 각 열(column)을 하나의 원소로 취급하고, 함께 남겨 두어도 모든 행이 여전히 정렬 상태를 유지하는 열들의 최장 증가 부분 수열(LIS)을 구하는 동적 계획법(DP)으로 해결할 수 있습니다. 남길 수 있는 열의 최대 개수를 구한 뒤 전체 열 개수에서 이를 빼면, 곧 최소 삭제 횟수가 됩니다.

구체적인 풀이 단계는 다음과 같습니다.

  • ret := 0으로 초기화합니다.
  • n := 배열 A의 크기
  • m := A[0]의 길이
  • 크기가 (m + 1)인 배열 lis를 선언하고 모든 값을 1로 채웁니다.
  • i := 0부터 i < m인 동안(i는 1씩 증가) 아래를 반복합니다.
    • j := 0부터 j < i인 동안(j는 1씩 증가) 아래를 반복합니다.
      • ok := true로 설정합니다.
      • k := 0부터 k < n인 동안(k는 1씩 증가) 아래를 반복합니다.
        • 만약 A[k][j] > A[k][i]라면, ok := false로 변경하고 반복문을 빠져나갑니다.
      • ok가 참이라면 아래를 수행합니다.
        • lis[i] := max(lis[j] + 1, lis[i])
        • ret := max(ret, lis[i])
  • ret이 0과 같다면 m - 1을 반환합니다.
  • 그 외의 경우에는 m - ret을 반환합니다.

여기서 핵심 아이디어는 다음과 같습니다. 열 j와 열 i를 동시에 남겼을 때 모든 행에서 A[k][j] <= A[k][i]가 성립한다면, 두 열은 체인으로 연결될 수 있습니다. 시간 복잡도는 세 개의 중첩 반복문으로 인해 O(n × m²)이 되며, 문자열 개수와 길이가 크지 않은 제약 조건에서는 충분히 효율적입니다.

C++ 구현 예시

아래의 구현 코드를 살펴보면 이해에 도움이 됩니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minDeletionSize(vector<string>& A){
      int ret = 0;
      int n = A.size();
      int m = A[0].size();
      vector<int> lis(m + 1, 1);
      for (int i = 0; i < m; i++) {
         for (int j = 0; j < i; j++) {
            bool ok = true;
            for (int k = 0; k < n; k++) {
               if (A[k][j] > A[k][i]) {
                  ok = false;
                  break;
               }
            }
            if (ok) {
               lis[i] = max(lis[j] + 1, lis[i]);
               ret = max(ret, lis[i]);
            }
         }
      }
      if (ret == 0)
      return m - 1;
      return m - ret;
   }
};
main(){
   Solution ob;
   vector<string> v = {"cbcdb","ccbxc"};
   cout << (ob.minDeletionSize(v));
}

입력

{"cbcdb","ccbxc"}

출력

3

예제 동작 분석

입력 ["cbcdb", "ccbxc"]의 경우 각 열은 (c,c), (b,c), (c,b), (d,x), (b,c)입니다. 예를 들어 0번 열과 3번 열을 함께 남기면 각 행은 "cd", "cx"가 되어 정렬 조건을 만족하지만, 세 개 이상의 열로는 체인을 구성할 수 없습니다. 따라서 최대 2개의 열만 남길 수 있으므로, 전체 5개의 열 중 3개를 삭제해야 하며 정답은 3이 됩니다.