두 개의 문자열 str1과 str2가 주어졌을 때, 두 문자열에서 공통으로 등장하는 문자의 개수를 구하는 것이 목표입니다. 즉, str1[i]와 str2[j]가 서로 같으면 한 쌍(pair)으로 간주하여 카운트를 1 증가시키고, 서로 다르면 카운트를 증가시키지 않습니다.
예시
입력 − str1 = "hello"
str2 = "heoo"
출력 − count is: 3
설명 − str1[0] = str2[0] (h), str1[1] = str2[1] (e), str1[2] ≠ str2[2] (l과 o), str1[3] = str2[3] (o)입니다. 따라서 동일한 문자로 이루어진 쌍은 3개이고, 서로 다른 문자로 이루어진 쌍은 1개입니다.
입력 − str1 = "point"
str2 = "print"
출력 − count is: 4
설명 − str1[0] = str2[0] (p), str1[1] ≠ str2[1] (o와 r), str1[2] = str2[2] (i), str1[3] = str2[3] (n), str1[4] = str2[4] (t)입니다. 따라서 동일한 문자로 이루어진 쌍은 4개이고, 서로 다른 문자로 이루어진 쌍은 1개입니다.
프로그램의 접근 방식
두 문자열 str1과 str2를 입력받습니다.
length() 함수를 사용해 두 문자열의 크기를 계산합니다. 이 함수는 공백을 포함한 문자열 내 문자 수에 해당하는 정수 값을 반환합니다.
먼저 두 문자열의 문자별 빈도 배열(frequency array)을 0으로 초기화합니다.
반복문을 돌며 "f1[str1[i] - 'a']++" 형태로 str1의 문자 빈도를 업데이트하고, str2에도 동일한 과정을 적용합니다.
공통 문자 쌍의 개수를 계산하기 위해 각 알파벳 위치마다 f1과 f2에 대해 min() 함수를 적용합니다. 두 문자열 중 더 적게 등장한 횟수만큼만 쌍이 성립하기 때문입니다.
최종 결과를 출력합니다.
예제 코드
#include <iostream>
using namespace std;
// 유효한 인덱스 쌍의 개수를 세는 함수
int pairs(string str1, int size1, string str2, int size2){
// str1과 str2의 문자 빈도를 저장할 f1, f2
int f1[26] = { 0 };
int f2[26] = { 0 };
// 유효한 쌍의 개수를 저장할 변수 'c'
int i, c = 0;
// str1과 str2의 문자 빈도 업데이트
for (i = 0; i < size1; i++){
f1[str1[i] - 'a']++;
}
for (i = 0; i < size2; i++){
f2[str2[i] - 'a']++;
}
// 유효한 쌍의 개수 계산
for (i = 0; i < 26; i++){
c += (min(f1[i], f2[i]));
}
return c;
}
// 메인 함수
int main(){
string str1 = "tutorialspoint", str2 = "codingground";
int size1 = str1.length(), size2 = str2.length();
cout<<"str1[i]=str2[j]인 총 쌍의 개수: ";
cout << pairs(str1, size1, str2, size2);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
str1[i]=str2[j]인 총 쌍의 개수 − 6
이 방법은 시간 복잡도 O(n + m)(n과 m은 각 문자열의 길이)로 두 문자열을 한 번씩만 순회하면 되기 때문에 매우 효율적입니다. 또한 알파벳 소문자 26개만 고려하면 되므로 추가 메모리 사용량도 일정하게 유지됩니다.