[C언어] Anagram (문자열 해싱 기반 탐색 알고리즘)

문제

Anagram

Anagram은 단어나 문장을 구성하고 있는 문자의 순서를 바꾸어 다른 단어나 문장을 만드는 것입니다. (예시: heart <=> earth / I am Lord Voldemort <=> Tom Marvolo Riddle) 사용자로부터 문자열을 입력받아서 주어진 사전 내에서 anagram을 이루는 단어가 있는지 확인하여 출력하세요.

• 사전은 repository에 주어진 american-english-large.txt 파일을 읽어서 사용하세요.
• 입력으로는 영문 대소문자로 구성된 한 단어만 들어온다고 가정합니다. (특수문자 및 공백 입력은 없습니다.)
• 매칭 시에 대소문자는 무시하고 처리하세요.
• 사전에서 anagram을 이루는 첫 번째 단어만 모두 소문자로 출력하세요.
• Anagram을 이루는 단어가 없을 경우 -1을 출력해주세요.

입출력 예시

(입력 #1)

ahalaaicpp

(출력 #1)

appalachia

 

(입력 #2)

gajae

(출력 #2)

-1

 

어떻게 풀까?

가장 단순한 방법은 가능한 모든 경우의 수를 다 만들고 비교해보면서 찾는 방법이지만, 그렇게 하면 너무 시간이 오래 걸리고 메모리도 많이 잡아먹고 가장 안좋은 방법이기 때문에 다른 방법을 생각해보자.

주어진 단어와 답이 되는 단어의 차이점은 순서이다. 따라서 구성 요소는 동일하다. 그렇다면 동일한 구성 요소를 갖는 단어를 찾아내면 될 것이다.

 

코드를 살펴보자

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define ll long long
char target[1010];
ll alcnt[27]={0};//알파벳 개수 세는 부분
char word[101];
int main(int argc, char *argv[]) {
	scanf("%s",word);
	int len = strlen(word);
	for(int i=0; i<len; i++)
	{
		alcnt[(int)(toupper(word[i])-'A')]++;
	}
	FILE *file = fopen("american-english-large.txt","r");
	while(fgets(target, sizeof(target),file) != NULL)
	{
		
		target[strcspn(target,"\n")] = '\0';
		int tlen = strlen(target);
		ll talcnt[27]={0};
	
		for(int i=0; i<tlen; i++)
		{
			if(isalpha(target[i]))
				talcnt[(int)(toupper(target[i])-'A')]++;
			else
				break;
		}
		///////////////////// 알파벳 개수 저장
		for(int i=0; i<27; i++)
		{
			if(talcnt[i] != alcnt[i])
				break;
			if(i==26)
			{
				target[0] = tolower(target[0]);
				printf("%s\n",target);
				return 0;
			}
		}
	}
	printf("-1\n");
	return 0;
}

 

코드는 이렇다. 크게 함수도 따로 짜지 않았고, 논리구조도 크게 어렵진 않다.

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define ll long long
char target[1010];
ll alcnt[27]={0};//알파벳 개수 세는 부분
char word[101];
int main(int argc, char *argv[]) {
	scanf("%s",word);
	int len = strlen(word);
	for(int i=0; i<len; i++)
	{
		alcnt[(int)(toupper(word[i])-'A')]++;
	}

이 부분은 입력받을 문자열의 구성 요소의 개수를 세서 저장하는 부분이다.

word배열에 입력을 받으면 반복문을 돌면서 alcnt함수에 A부터 Z까지의 개수가 저장될 것이다.

 

	FILE *file = fopen("american-english-large.txt","r");
	while(fgets(target, sizeof(target),file) != NULL)
	{
		
		target[strcspn(target,"\n")] = '\0';
		int tlen = strlen(target);
		ll talcnt[27]={0};
	
		for(int i=0; i<tlen; i++)
		{
			if(isalpha(target[i]))
				talcnt[(int)(toupper(target[i])-'A')]++;
			else
				break;
		}

이 부분은 파일을 열어서 한줄씩 입력받는 부분이다.

여기서 fopen을 이전 과제에서 argv[1]로 파일 이름을 받아서 동일하게 했다가 영문도 모르고 40분간 seg fault를 경험하였다.

한 줄 씩 입력을 받고 해당 문자열에서 특수문자가 나오면 넘어가고, 알파벳의 개수를 세준다.

 

		for(int i=0; i<27; i++)
		{
			if(talcnt[i] != alcnt[i])
				break;
			if(i==26)
			{
				target[0] = tolower(target[0]);
				printf("%s\n",target);
				return 0;
			}
		}
		
	}
	printf("-1\n");
	return 0;
}

이 부분은 위에서 센 알파벳의 개수가 서로 맞는지 판단하는 부분이다. 만약 같지 않은 부분이 나오게 된다면 코드를 중지하고 다음으로 넘어간다.

만약 끝까지 돌았다면 target단어를 출력하고 코드를 종료,

끝까지 찾지 못하면 -1을 출력하고 종료한다.