두 개의 문자열 str1과 str2가 주어졌다고 가정해 보겠습니다. str2는 str1의 부분 문자열(substring)이며, str1에서 이를 삭제할 수 있습니다. 또한 str2는 str1 안에 여러 번 등장할 수도 있습니다.
우리의 목표는 str1에서 str2를 계속해서 제거했을 때, 최종적으로 str1이 빈 문자열(null string)이 되는지 판별하는 것입니다. 빈 문자열이 될 수 있다면 1을, 그렇지 않다면 0을 반환하면 됩니다.
예를 들어 입력이 str1 = "CCCPPPPPP", str2 = "CPP"라고 해봅시다. 그러면 출력은 true(1)가 됩니다.
문제 해결 접근 방식
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- str1의 길이가 0보다 큰 동안 아래 과정을 반복합니다.
- index := str2가 str1 내에서 처음 등장하는 시작 위치를 찾습니다.
- 만약 index가 -1이라면(str2가 더 이상 존재하지 않으면) 반복문을 종료합니다.
- str1에서 해당 위치의 str2를 삭제합니다.
- 반복이 끝난 후 str1의 길이가 0이면 1을, 아니면 0을 반환합니다.
C++에서는 string::find() 함수로 부분 문자열의 위치를 찾고, string::erase() 함수로 해당 구간을 삭제할 수 있으므로 매우 간결하게 구현됩니다.
예제 코드 (C++)
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
#include<bits/stdc++.h>
using namespace std;
bool solve(string str1, string str2) {
while (str1.size() > 0) {
int index = str1.find(str2);
if (index == -1)
break;
str1.erase(index, str2.size());
}
return (str1.size() == 0);
}
int main() {
string str1 = "CCCPPPPPP", str2 = "CPP";
cout<<solve(str1, str2)<<endl;
return 0;
}입력
"CCCPPPPPP", "CPP"
출력
1
코드 설명
- solve() 함수는 str1에서 str2를 찾아 삭제하는 작업을 반복 수행합니다.
str1.find(str2)는 str2가 발견된 첫 번째 위치를 반환하며, 찾지 못하면 -1을 반환합니다.str1.erase(index, str2.size())는 index 위치부터 str2의 길이만큼 문자를 제거합니다.- 모든 반복이 끝난 후 str1이 완전히 비었다면 true(1), 남은 문자가 있다면 false(0)를 반환합니다.
위 예제에서 "CCCPPPPPP"에서 "CPP"를 반복적으로 제거하면 결국 모든 문자가 사라지므로 결과는 1이 출력됩니다.