두 개의 문자열 S와 T가 주어졌을 때, S가 T의 부분 수열(subsequence)인지 판별해야 합니다. 부분 수열이란 원본 문자열에서 문자들을 순서를 유지한 채 일부를 선택해 만든 문자열을 의미하며, 선택된 문자들이 반드시 연속될 필요는 없습니다.
예를 들어 S = "abc", T = "adbrcyxd"라고 가정해 보겠습니다. T 안에서 'a' → 'b' → 'c' 순서로 문자가 등장하므로 결과는 True가 됩니다.
접근 방법
이 문제는 투 포인터(two pointer) 기법으로 선형 시간에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 긴 문자열을 한 번만 순회하면서, 찾고자 하는 문자열의 문자를 순서대로 매칭하는 것입니다. 단계별 과정은 다음과 같습니다.
- S와 T가 완전히 같다면 true를 반환합니다.
- n := S의 길이, m := T의 길이로 설정하고, 매칭 진행 위치를 나타내는 포인터 j := 0으로 초기화합니다.
- i를 0부터 n-1까지 증가시키며 다음을 반복합니다.
- T[j]와 S[i]가 같다면 j를 1 증가시킵니다.
- j가 T의 길이와 같아지면 S의 모든 문자를 순서대로 찾은 것이므로 true를 반환합니다.
- 루프가 종료될 때까지 true가 반환되지 않았다면 false를 반환합니다.
아래 코드에서 solve(t, s) 함수는 "t가 s의 부분 수열인지"를 검사하며, main 함수에서 solve(S, T) 형태로 호출하여 S가 T의 부분 수열인지 확인합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(string t, string s) {
if(s == t)
return true;
int n = s.size();
int m = t.size();
int j = 0;
for(int i = 0; i < n; i++){
if(t[j] == s[i])
j++;
if(j == t.size())
return true;
}
return false;
}
};
main(){
Solution ob;
string S = "abc", T = "adbrcyxd";
cout << ob.solve(S, T);
}입력
"abc", "adbrcyxd"
출력
1
출력값 1은 bool 타입의 true를 의미합니다. 즉, "abc"는 "adbrcyxd"의 부분 수열이라는 뜻입니다.
복잡도 분석
긴 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가적인 자료구조 없이 포인터 변수만 사용하므로 공간 복잡도는 O(1)입니다.