문제 소개
이번 문제에서는 두 개의 문자열 str1과 str2가 주어지며, str2의 모든 문자가 str1 안에 존재하는지 판별하는 것이 목표입니다.
먼저 예시를 통해 문제를 살펴보겠습니다.
입력 −
str1 = "Hello"
str2 = "Hell"
출력 − yes
설명 − str2의 모든 문자(H, e, l, l)가 str1에 포함되어 있으므로 결과는 yes입니다.
효율적인 해결 방법: 빈도 배열 활용
가장 단순한 방법은 str2의 각 문자를 str1에서 일일이 찾아보는 것입니다. 하지만 이 방식은 두 문자열이 길어질수록 탐색 시간이 크게 늘어나 비효율적입니다.
더 나은 성능을 위해 빈도 배열(frequency array)을 활용할 수 있습니다. 유효한 모든 문자를 커버할 수 있도록 크기 256의 배열을 준비하고, 다음 순서로 진행합니다.
- str1을 순회하며 등장하는 각 문자에 해당하는 빈도 배열의 값을 1씩 증가시킵니다.
- str2를 순회하며 각 문자에 해당하는 빈도 값을 1씩 감소시킵니다.
- 감소 후 값이 음수가 되면 str1에 해당 문자가 부족하다는 의미이므로 즉시 false를 반환합니다.
- 모든 문자를 통과하면 str2의 모든 문자가 str1에 존재하므로 true를 반환합니다.
이 방식은 두 문자열을 각각 한 번씩만 순회하므로 시간 복잡도는 O(n + m)이고, 고정 크기 배열만 사용하므로 공간 복잡도는 O(1)입니다. 또한 빈도를 차감하는 방식 덕분에 str2에 중복 문자가 있을 때도 정확하게 판별할 수 있습니다.
구현 예제
위 해결 방법을 C++로 구현한 프로그램입니다.
#include <iostream>
#include <string.h>
using namespace std;
bool isPresent(string str1, string str2){
int freq[256] = { 0 };
for (int i = 0; i < str1.length(); i++)
freq[str1[i]]++;
for (int i = 0; i < str2.length(); i++) {
freq[str2[i]]--;
if (freq[str2[i]] < 0)
return false;
}
return true;
}
int main() {
string str1 = "tutorialspoint";
string str2 = "point";
cout<<"'"<<str2<<"'의 모든 문자는 '"<<str1<<"'에 ";
isPresent(str1,str2)?cout<<"포함되어 있습니다":cout<<"포함되어 있지 않습니다";
return 0;
}
실행 결과
'point'의 모든 문자는 'tutorialspoint'에 포함되어 있습니다
마무리
빈도 배열을 사용하면 각 문자열을 한 번씩만 순회해도 원하는 결과를 얻을 수 있어, 완전 탐색 방식보다 훨씬 효율적입니다. 문자 포함 여부를 검사하는 유사한 문제에서도 널리 활용되는 패턴이므로 잘 기억해 두면 좋습니다.