서로 다른 두 문자열 s1과 s2가 주어졌을 때, 어느 한쪽에서 문자를 정확히 하나 제거하여 다른 쪽 문자열과 같아지는 경우의 수를 구하는 것이 이 문제의 목표입니다.
예시
입력 - string S1 = "utter", string S2 = "butter";
출력 - 한 글자를 제거한 후 두 문자열 중 하나와 같아지는 경우의 수: 1
설명 - S2("butter")에서 문자 'b'를 제거하면 "utter"가 되어 S1과 완전히 같아집니다. 따라서 가능한 경우의 수는 1입니다.
입력 - string S1 = "fat", string S2 = "rat";
출력 - 한 글자를 제거한 후 두 문자열 중 하나와 같아지는 경우의 수: 2
설명 - S1("fat")에서 'f'를 제거하면 "rat"이 되어 S2와 같아지고, 반대로 S2("rat")에서 'r'을 제거하면 "fat"이 되어 S1과 같아집니다. 양방향 모두 가능하므로 경우의 수는 2입니다.
알고리즘 접근 방식
- 두 문자열 s1과 s2를 선언하고, s1의 길이를 계산하여 처리 함수에 전달합니다.
- 변수 count를 선언하고 최대 가능 값인 2로 초기화합니다. 한 번의 제거로 두 문자열이 일치할 수 있는 경우는 최대 2가지(각 문자열에서 하나씩)이기 때문입니다.
- 루프 탐색을 위한 임시 변수 start와 end를 선언합니다.
- 첫 번째 FOR 루프를 0부터 s1의 길이까지 실행하며, s1[i]와 s2[i]가 다른 첫 번째 위치를 찾으면 start에 저장하고 루프를 종료합니다.
- 두 번째 FOR 루프를 s1의 길이 - 1부터 역순으로 실행하며, 마지막으로 일치하지 않는 위치를 찾으면 end에 저장하고 루프를 종료합니다.
- end가 start보다 작다면 두 문자열이 이미 동일한 상태이므로, count를 26 * (s1의 길이 + 1)로 설정한 후 반환합니다.
- 그렇지 않고 start == end라면 불일치 지점이 하나뿐이라는 의미이므로 count(2)를 그대로 반환합니다.
- 위 조건에 해당하지 않는 경우, start + 1부터 end까지 순회하며 s1[i] != s2[i - 1]인지 검사하고, 참이면 count를 1 감소시킨 후 루프를 종료합니다.
- 같은 범위에서 s1[i - 1] != s2[i]인지 검사하는 또 다른 루프를 실행하고, 참이면 count를 1 감소시킨 후 루프를 종료합니다.
- 최종 count 값을 반환합니다.
- 결과를 출력합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int equal_removal(string S1, string S2, int size_S1) {
int count = 2;
int start;
int end;
for (int i = 0; i < size_S1; ++i) {
if (S1[i] != S2[i]) {
start = i;
break;
}
}
for (int i = size_S1 - 1; i >= 0; i--) {
if (S1[i] != S2[i]) {
end = i;
break;
}
}
if (end < start) {
count = 26 * (size_S1 + 1);
return count;
} else if (start == end) {
return count;
} else {
for (int i = start + 1; i <= end; i++) {
if (S1[i] != S2[i - 1]) {
count--;
break;
}
}
for (int i = start + 1; i <= end; i++) {
if (S1[i - 1] != S2[i]) {
count--;
break;
}
}
return count;
}
}
int main() {
string S1 = "utter";
string S2 = "butter";
int size_S1 = S1.length();
cout << "Count of strings that become equal to one of the two strings after one removal are: " << equal_removal(S1, S2, size_S1);
return 0;
}위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
출력
Count of strings that become equal to one of the two strings after one removal are: 1