[Algorithm] 16. Anagram(아나그램 : 구글 인터뷰 문제)

인트로

문자열을 다루는 알고리즘을 소개하려 한다.

까다롭게 시간제한이 있는 문제는 아니다.

깊게 생각하고 고민하고 문제를 해결할 수 있다면 되는 문제가 아닐까 한다. 

해결했다면 자랑스러워 하자! 무려 구글 인터뷰 문제라고 한다.

 

Anagram(아나그램) : 구글 인터뷰 문제

Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 한다.

문제

AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면 A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다.
즉 어느 한 단어를 재배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다.
길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세요.
아나그램 판별시 대소문자가 구분됩니다.

※ 입력설명
첫 줄에 첫 번째 단어가 입력되고, 두 번째 줄에 두 번째 단어가 입력됩니다. 단어의 길이는 100을 넘지 않습니다.

※ 출력설명
두 단어가 아나그램이면 “YES"를 출력하고, 아니면 ”NO"를 출력합니다.

입력

AbaAeCe
baeeACA

출력

YES

코드 설명

해결 방법은 여러 가지가 있겠지만 나의 코드는 A~Z, a~z 각각의 알파벳 수를 vector에 저장하는 방식으로 이루어진다.

vector의 길이는 52(소문자 26 대문자 26)이다. 0~25는 대문자, 26~51은 소문자를 위해 저장된다.

calAlphabet 함수에 문자열과 벡터를 넘겨주면 문자에 대응되는 vector의 인덱스에 알파벳의 개수가 저장된다.

마무리로 두 벡터가 같은지 검사하면 아나그램인지 판별가능하다.

#include <iostream>
#include <vector>

#define ALPHABET 52

using namespace std;

void calAlphabet(string str, vector<char> &vec)
{
	for (int i = 0; i < str.size(); i++)
	{
		if (str[i] >= 'A' && str[i] <= 'Z')
			vec[str[i] - 'A']++;
		else if (str[i] >= 'a' && str[i] <= 'z')
			vec[str[i] - 'a' + 26]++;
	}
}

int main()
{
	string str;
	vector<char> a(ALPHABET), b(ALPHABET);
	
	cin >> str;
	calAlphabet(str, a);
	
	cin >> str;
	calAlphabet(str, b);

	for (int i = 0; i < ALPHABET; i++)
	{
		if (a[i] != b[i])
		{
			cout << "NO";
			return 0;
		}
	}
	
	cout << "YES";
	return 0;
}