아나그램(Anagram)이란 무엇일까요?
아나그램(anagram)이란 두 문자열에 포함된 모든 문자가 동일한 횟수만큼 등장하는 관계를 말합니다. 즉, 문자열의 순서는 달라도 어떤 문자가 몇 번씩 사용되었는지가 완전히 같다면, 그 두 문자열은 서로 아나그램 관계라고 할 수 있습니다.
두 문자열이 아나그램인지 확인하려면 다음 과정을 거칩니다.
먼저 사용자로부터 두 개의 문자열을 입력받습니다. 그다음 각 알파벳('a'부터 'z'까지)이 각 문자열에 몇 번 등장하는지 빈도수를 계산합니다. 여기서 빈도(frequency)란 특정 알파벳이 문자열 안에 나타난 횟수를 의미합니다. 마지막으로 두 문자열의 알파벳별 빈도수를 하나씩 비교합니다.
모든 알파벳에 대해 빈도수가 완전히 일치한다면, 두 문자열은 아나그램입니다. 반대로 단 하나의 알파벳이라도 빈도수가 다르다면 아나그램이 아닙니다.
예제 1: 아나그램인 경우
- 문자열 1: abcd
- 문자열 2: bdac
두 문자열은 동일한 문자들이 각각 한 번씩 등장하므로 아나그램입니다.
예제 2: 아나그램이 아닌 경우
- 문자열 1: programming
- 문자열 2: gramming
출력 결과: 두 문자열은 아나그램이 아닙니다. 'programming'에는 'gramming'에 없는 'p'와 'o'가 추가로 포함되어 있어 빈도수가 일치하지 않기 때문입니다.
아나그램 판별 C 프로그램
다음은 두 문자열이 아나그램인지 판별하는 C 프로그램입니다. 길이 26의 정수 배열 두 개를 사용해 각 문자열의 알파벳 빈도수를 저장한 뒤 비교하는 방식으로 동작합니다.
#include <stdio.h>
int check_anagram(char [], char []);
int main(){
char a[1000], b[1000];
printf("Enter two strings\n");
gets(a);
gets(b);
if (check_anagram(a, b))
printf("The strings are anagrams.\n");
else
printf("The strings aren't anagrams.\n");
return 0;
}
int check_anagram(char a[], char b[]){
int first[26] = {0}, second[26] = {0}, c=0;
// 첫 번째 문자열의 문자 빈도수 계산
while (a[c] != '\0') {
first[a[c]-'a']++;
c++;
}
c = 0;
while (b[c] != '\0') {
second[b[c]-'a']++;
c++;
}
// 문자 빈도수 비교
for (c = 0; c < 26; c++)
if (first[c] != second[c])
return 0;
return 1;
}코드 동작 원리
- 빈도수 계산: 문자에서 'a'를 빼면 해당 알파벳의 인덱스(0~25)가 되므로, 이를 활용해 배열 위치마다 등장 횟수를 증가시킵니다.
- 빈도수 비교: 26개의 알파벳 슬롯을 순회하며 두 배열의 값이 모두 같은지 확인하고, 하나라도 다르면 0(거짓)을 반환합니다.
- 시간 복잡도: 문자열 길이에 비례하여 O(n) 시간에 처리되므로 매우 효율적입니다.
참고: 예제 코드에 사용된 gets() 함수는 버퍼 오버플로우 위험 때문에 현재 C 표준에서 제거되었습니다. 실제 프로젝트에서는 fgets()와 같은 안전한 입력 함수를 사용하는 것이 좋습니다.
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
Run 1: Enter two strings abcdef deabcf The strings are anagrams. Run 2: Enter two strings tutorials Point The strings aren't anagrams.
첫 번째 실행에서는 'abcdef'와 'deabcf'가 모든 알파벳의 빈도수가 같아 아나그램으로 판별되었고, 두 번째 실행에서는 'tutorials'와 'Point'의 문자 구성이 달라 아나그램이 아니라고 판별된 것을 확인할 수 있습니다.