4-1 애너그램 판별 프로그램

애너그램이란 문자의 구성은 같고, 배치 또는 뜻만 다른 문자열을 의미합니다.

버블 정렬 알고리즘을 이용하여 5개의 숫자로 구성된 문자열 애너그램을 판별하는 프로그램을 작성해보았습니다.

 

#include <stdio.h>
#include <string.h>
#define SIZE 5 
 
int check_anagram(char anagram[][6]);

int main() {
    // 문자열의 끝인 null값까지 포함하여 6열까지 공간을 할당해줘야함. 
	char anagram[2][6] = {"11132", "21131"}; 
	if(check_anagram(anagram)) 
		printf("Anagram True\n");
	else 
		printf("Anagram False\n");
}

 

정렬 후 문자열이 같은지 비교하기 위하여 strcmp 함수를 사용해야 하므로 string.h를 포함시켜주었고,

정렬 알고리즘 반복문의 조건에 사용되는 기호 상수 SIZE를 정의해 주었습니다.

​

문자열을 정렬했을 때 문자 구성이 같은지 판별해 주는 애너그램 판별 함수 check_anagram 함수를 선언해 주었습니다. 참이면 1, 거짓이면 0을 반환해 줄 것입니다.

​

문자열의 길이를 5바이트로 제한을 두는 2행 6열 2차원 배열을 선언해 주었으며, 여기서 [2][6]인 이유는 문자열 리터럴의 끝을 알려주는 '\0'(=NULL) 값이 오기 때문에 5바이트에서 1바이트를 추가로 할당해 주었습니다.

2차원 배열을 check_anagram 함수에 인자로 전달하여 두 문자열이 애너그램이라면 True를,

애너그램이 아니라면 False를 출력하게 될 것입니다.

 

int check_anagram(char anagram[][6]) { // 각 문자의 아스키코드 값을 버블정렬로 오름차순 정렬 
	int i, j;
	char temp; 
	
	printf("정렬 전: %s\t%s\n",anagram[0], anagram[1]);
	
	for(i = 0; i<SIZE; i++) {
		for(j = 0; j< SIZE-i-1; j++) {
			if(anagram[0][j]>anagram[0][j+1]) {
				temp = anagram[0][j];
				anagram[0][j] = anagram[0][j+1];
				anagram[0][j+1] = temp;
			}
			
			if(anagram[1][j]>anagram[1][j+1]) {
				temp = anagram[1][j];
				anagram[1][j] = anagram[1][j+1];
				anagram[1][j+1] = temp;
			}
		}
	}
	
	printf("정렬 후: %s\t%s\n",anagram[0], anagram[1]);
	
	if(strcmp(anagram[0], anagram[1]) == 0) 
		return 1;
	else

 

정수형 배열 두 개를 선언하여 정렬 후 마지막에 반복문으로 애너그램인지 판별할 수도 있었겠지만,

저의 경우 char형으로 5개의 숫자를 한 쌍으로 묶어서 각각의 문자에 대응되는 아스키코드 값을 비교시켜서

마지막 반복문을 사용하지 않고 strcmp 함수로 판별하였습니다.

​

버블 정렬은 두 개의 인접한 원소끼리 비교하여 오름차순일 경우 더 작은 원소를 앞으로 보내는 정렬 알고리즘으로,

이 과정을 반복하면 마지막에는 가장 큰 값이 맨 뒤로 이동하게 되고 맨 앞에서부터 작은 원소를 시작으로 나열됩니다. 버블 정렬의 시간 복잡도는 상한일 때 O(n^2)이며, 하한일 때(이미 정렬되어 있는 경우) O(n^2)을 가집니다.

​

정렬이 끝난 후에는 anagram[0]과 anagram[1]의 문자 구성이 똑같은지 비교해서 애너그램이라면 1을,

아니라면 0을 반환합니다.

​

출력 결과는 다음과 같습니다.

 

​

​

​

정렬 알고리즘에는 버블 정렬 이외에 삽입, 선택, 퀵, 병합 정렬 등 다양한 알고리즘이 있지만

무난하고 구현하기 쉬운 버블 정렬을 이용해보았습니다.

​

다음에는 알고리즘 연습도 해볼 겸 여러 방법으로 구현해보겠습니다. 감사합니다.