LIS 변형 적용으로 열 삭제 최소 개수 문제 O(n*m²) 시간에 해결함

Context

n개의 동일 길이 문자열 배열에서 열을 삭제하여 각 행(row)이 개별적으로 사전순 정렬되도록 하는 문제임. 전체 문자열 간 순서는 고려하지 않으며, 삭제할 열 개수의 최솟값을 반환해야 함.

Technical Solution

• Dynamic Programming: dp[col] 배열을 사용하여 col 위치까지 보존 가능한 최대 열 개수를 계산함
• LIS 변형 적용: 두 열 j와 col 사이에서 모든 행의 문자가 prev <= curr 조건을 만족하는지 검증함
• 삼중 중첩 루프 구조: col 순회, j 순회, 행 순회로 O(n*m²) 시간 복잡도를 가짐
• 정렬 후 최대값 추출: dp 배열 정렬 후 최대값으로 보존 열 수 결정함
• 삭제 개수 산출: 전체 길이에서 보존 가능한 최대 열 수를 빼서 최소 삭제 개수를 계산함

Impact

수치 기반 성과 없음.

Key Takeaway

LIS 문제의 기본 패턴인 "이전 상태와 현재 상태 비교 후 최적 부분 구조 활용"을 인식하면, 문자열 정렬 제약 조건 문제로 확장 적용할 수 있음. 열 간 문자 비교 로직만 추가하여 LIS를 열 보존 최적화 문제로 변환함.