문제 개요
이 프로그래밍 문제에서는 두 개의 문자열이 주어집니다. 우리가 해야 할 일은 두 문자열에 공통으로 포함된 모든 문자를 찾아 알파벳 순(사전순)으로 출력하는 것입니다. 만약 공통된 문자가 하나도 없다면 'NO COMMON CHARACTERS'를 출력합니다. 여기서는 문자열이 소문자 알파벳으로만 구성되어 있다고 가정합니다.
예시
입력 : string1 : adsfhslf
string2 : fsrakf
출력 : affs
설명 − 두 문자열에 공통으로 등장하는 문자는 a, f, s입니다. 각 문자는 두 문자열에서 등장한 횟수 중 더 적은 횟수만큼 출력되므로, 사전순 결과는 'affs'가 됩니다.
입력 : string1 : abcde
string2 : glhyte
출력 : No common characters
설명 − 두 문자열 사이에 공통으로 나타나는 문자가 전혀 없습니다.
이 문제를 해결하려면 두 문자열에서 공통으로 나타나는 문자를 찾은 뒤, 이를 사전순으로 정렬하여 출력해야 합니다.
알고리즘
이 문제를 해결하기 위한 알고리즘은 다음과 같습니다.
1단계 : 크기가 26인 두 배열 a1[]과 a2[]를 생성하여 각각 string1과 string2에 포함된 알파벳의 빈도를 카운트합니다.
2단계 : a1[]과 a2[]를 차례대로 순회하면서, 두 배열 모두에서 값이 0이 아닌 인덱스에 해당하는 문자를 최소 등장 횟수만큼 순서대로 출력합니다.
구현 예제
위 알고리즘을 바탕으로 실제 동작 과정을 보여주는 프로그램을 작성해 보겠습니다.
#include<bits/stdc++.h>
using namespace std;
int main(){
string string1 = "adjfrdggs";
string string2 = "gktressd";
cout<<"The strings are "<<string1<<" and "<<string2;
cout<<"\nThe common characters are : ";
int a1[26] = {0};
int a2[26] = {0};
int i , j;
char ch;
char ch1 = 'a';
int k = (int)ch1, m;
for(i = 0 ; i < string1.length() ; i++){
a1[(int)string1[i] - k]++;
}
for(i = 0 ; i < string2.length() ; i++){
a2[(int)string2[i] - k]++;
}
for(i = 0 ; i < 26 ; i++){
if (a1[i] != 0 and a2[i] != 0){
for(j = 0 ; j < min(a1[i] , a2[i]) ; j++){
m = k + i;
ch = (char)(k + i);
cout << ch;
}
}
}
return 0;
}
코드 설명
- 배열 a1[]과 a2[]는 각 문자열에서 'a'부터 'z'까지의 알파벳이 몇 번 등장했는지를 저장합니다.
- 문자를 배열 인덱스로 변환할 때는 해당 문자의 ASCII 값에서 'a'의 ASCII 값을 빼면 됩니다.
- 마지막 반복문에서 특정 인덱스의 두 카운트가 모두 0이 아니라면, 그 알파벳은 두 문자열에 공통으로 존재한다는 의미입니다.
- min(a1[i], a2[i])만큼 문자를 출력하기 때문에 중복 문자도 올바르게 처리됩니다.
출력
The strings are adjfrdggs and gktressd
The common characters are : dgrs
복잡도 분석
시간 복잡도는 두 문자열을 한 번씩 순회하고 26개의 배열 요소만 확인하므로 O(n + m)입니다(n, m은 각 문자열의 길이). 공간 복잡도는 크기 26의 배열 두 개만 사용하므로 O(1)로 상수 공간입니다.