두 개의 문자열이 주어졌을 때, 이 문자열들의 가장 긴 비공통 부분 수열(Longest Uncommon Subsequence)의 길이를 구하는 문제입니다. 여기서 '비공통 부분 수열'이란 한 문자열의 부분 수열 중에서 다른 문자열에는 나타나지 않는 것을 의미합니다. 즉, 한쪽 문자열에서만 찾을 수 있는 가장 긴 부분 수열의 길이를 구해야 하며, 만약 그러한 부분 수열이 존재하지 않는다면 -1을 반환해야 합니다.
예를 들어 입력이 "aabbac"와 "aabbcc"라면, 출력은 6이 됩니다.
문제 해결 접근 방법
이 문제는 언뜻 복잡해 보이지만, 사실 매우 간단한 관찰 하나로 해결할 수 있습니다.
- 두 문자열이 완전히 같은 경우: 어떤 부분 수열을 선택하더라도 반드시 다른 문자열에도 나타나므로, 비공통 부분 수열은 존재하지 않습니다. 따라서 -1을 반환합니다.
- 두 문자열이 다른 경우: 더 긴 문자열 전체가 곧 정답이 됩니다. 더 긴 문자열은 짧은 문자열의 부분 수열일 수 없기 때문입니다. 두 문자열의 길이가 같지만 내용이 다른 경우에도, 문자열 전체 자체가 서로의 부분 수열이 아니므로 마찬가지로 두 길이 중 최댓값을 반환하면 됩니다.
정리하면 알고리즘은 다음과 같습니다.
- a와 b가 동일한지 비교합니다.
- 동일하다면 -1을 반환합니다.
- 동일하지 않다면 a.size()와 b.size() 중 최댓값을 반환합니다.
C++ 구현 예제
아래 코드를 통해 구현 방법을 더 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findLUSlength(string a, string b) {
if (a == b)
return -1;
else
return max(a.size(), b.size());
}
};
main(){
Solution ob;
cout << (ob.findLUSlength("aabbac","aabbcc"));
}입력
"aabbac","aabbcc"
출력
6
코드 설명 및 시간 복잡도
위 코드는 먼저 두 문자열이 같은지 확인하고, 같지 않다면 max() 함수를 사용해 두 문자열 길이 중 큰 값을 그대로 반환합니다. 입력 예제에서 "aabbac"와 "aabbcc"는 서로 다르고 길이가 모두 6이므로 결과로 6이 출력됩니다.
시간 복잡도는 문자열 비교 연산이 지배적이므로 O(min(N, M))이며, 공간 복잡도는 추가 메모리를 사용하지 않으므로 O(1)입니다. N과 M은 각각 문자열 a와 b의 길이입니다.