C++에서 가장 긴 비공통 부분 수열 II 찾기

문제 소개

문자열 리스트가 주어졌을 때, 그중에서 가장 긴 비공통 부분 수열(Longest Uncommon Subsequence)을 찾는 문제입니다. 여기서 비공통 부분 수열이란, 리스트에 있는 특정 문자열의 부분 수열이면서 동시에 다른 어떤 문자열의 부분 수열에도 해당하지 않는 것 중 가장 긴 것을 의미합니다.

부분 수열(subsequence)은 원래 시퀀스에서 나머지 요소들의 상대적인 순서를 변경하지 않고 일부 문자를 삭제함으로써 얻을 수 있는 시퀀스입니다.

이 문제에서는 문자열 리스트를 입력으로 받으며, 출력은 가장 긴 비공통 부분 수열의 길이입니다. 만약 조건을 만족하는 부분 수열이 존재하지 않는다면 -1을 반환해야 합니다.

예를 들어 입력이 "aba", "cdc", "eae"라면 세 문자열이 서로의 부분 수열이 아니므로 출력은 3이 됩니다.

알고리즘 접근 방법

이 문제를 해결하기 위해 다음 단계를 따릅니다.

isSubsequence(a, b) 함수를 정의합니다.
j := 0으로 초기화한 뒤, i := 0부터 a의 크기 미만일 때까지 i를 1씩 증가시키며 반복합니다. 이때 j가 b의 크기보다 작고 a[i]가 b[j]와 같다면 j를 1 증가시킵니다. 반복이 끝난 후 b의 크기와 j가 같으면 true를 반환합니다. 즉, a 안에서 b를 순서대로 찾을 수 있는지 확인하는 로직입니다.
getDuplicates(strs) 함수를 정의합니다.
visited 집합과 ret 집합을 준비합니다. i := 0부터 strs의 크기 미만일 때까지 반복하면서, strs[i]가 이미 visited에 존재한다면 ret에 strs[i]를 추가하고, 모든 경우에 strs[i]를 visited에 삽입합니다. 마지막에 ret을 반환합니다.
메인 메소드에서 다음 과정을 수행합니다.
먼저 strs 배열을 문자열 길이를 기준으로 내림차순 정렬합니다. 그리고 duplicates := getDuplicates(strs)로 중복 문자열 집합을 구합니다.
i := 0부터 strs의 크기 미만일 때까지 반복합니다.
- strs[i]가 duplicates에 포함되어 있다면 해당 반복은 건너뜁니다(continue).
- i가 0이라면 strs[i]의 길이를 바로 반환합니다.
- j := 0부터 j < i일 때까지 반복하면서 isSubsequence(strs[j], strs[i])가 false인 경우, j가 i - 1과 같다면 strs[i]의 길이를 반환합니다. 반면 결과가 true라면 루프를 빠져나갑니다(break).
위 과정을 모두 통과하지 못했다면 -1을 반환합니다.

핵심 아이디어

문자열을 길이 기준으로 내림차순 정렬하면 더 긴 문자열부터 검사하게 되므로, 자신보다 앞에 있는(더 긴) 문자열들의 부분 수열이 아닌 첫 번째 문자열이 곧 정답이 됩니다. 또한 중복된 문자열은 서로에게 부분 수열이 되므로 절대 답이 될 수 없어 미리 제외하는 것이 이 알고리즘의 핵심입니다.

구현 예시

더 잘 이해하기 위해 다음 C++ 구현 코드를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    static bool cmp(string a, string b){
        return a.size() > b.size();
    }
    int findLUSlength(vector<string>& strs){
        sort(strs.begin(), strs.end(), cmp);
        set<string> duplicates = getDuplicates(strs);
        for (int i = 0; i < strs.size(); i++) {
            if (duplicates.count(strs[i]))
                continue;
            if (i == 0)
                return strs[i].size();
            for (int j = 0; j < i; j++) {
                if (!isSubsequence(strs[j], strs[i])) {
                    if ((j == i - 1)) {
                        cout << i << endl;
                        return strs[i].size();
                    }
                }
                else
                break;
            }
        }
        return -1;
    }
    bool isSubsequence(string a, string b){
        int j = 0;
        for (int i = 0; i < a.size(); i++) {
            if (j < b.size() && a[i] == b[j])
                j++;
        }
        return j == b.size();
    }
    set<string> getDuplicates(vector<string>& strs){
        set<string> visited;
        set<string> ret;
        for (int i = 0; i < strs.size(); i++) {
            if (visited.count(strs[i])) {
                ret.insert(strs[i]);
            }
            visited.insert(strs[i]);
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<string> v = {"aba", "cdc", "eae"};
    cout << (ob.findLUSlength(v));
}

입력

{"aba", "cdc", "eae"}