C++ 아나그램 문제 풀기

아나그램이란?

- 한 단어의 철자를 분해해 다른 단어, 혹은 다른 문장으로 바꾸는 놀이를 의미

- 같은 영어 알파벳을 가지고도 다른 뜻을 가지는 단어를 만들수 있다는 것이죠.

 

God save us all(신은 우리 모두를 구하신다) → Salvaged soul(구원받은 영혼)

 

두개의 string을 비교하여 같은 수의 알파벳이 존재하면 true를 리턴 아닐 시 false 리턴

 

처음 접근 한 방법은 일단 최대한 쉽게 정답을 도출하고 더 좋은 방법을 생각하고자

무작정 2중 포문을 사용하여 전체를 비교하는 방법으로 접근하는 도중

string을 정렬하여 비교하는 방법을 떠올라 사용하였다.

정렬 후에 각각의 길이를 비교하여 for문을 들어가기전에 길이가 다를 경우

false를 반환하여 조금이라도 더 빠르게 계산할 수 있도록 하였다

기록으로 남기려고 집에서 visual studio로 작성하다보니 for문을 사용하지않고 비교하면 된다는걸

1분도 안되어 알게되어서 많이 후회되었다 좀 더 침착하게 풀어볼껄... 손코딩이여서 그랬을까..

막히던 순간에 방법이 갑자기 생각나서 답을 찾았다는 기쁨에 더욱 신중하게 접근하지 못한 것이 문제였던 것 같다...

 

스스로 생각하는 최종 코드

였는데...

시간 복잡도에 대하여 고민하다 보니

최종적으로 고친 코드에서 두개의 길이를 비교하는 과정을 생략해주어도 될 것같다는

생각이 나왔다 첫번째 코드에서는 for문으로 하나씩 비교하는 과정을 조금이라도 줄이기 위해

길이를 비교하여 1차적으로 확인하여 for문을 들어가기 전에 길이가 다르면 for문을 돌리지 않고 결과를

반환하는 것이였는데 수정한 코드는 for문을 돌지 않으니 그 과정 또한 필요하지 않다고 생각하게 되었다.

 

총 코드

#include<string>
#include<algorithm>
#include<iostream>
using namespace std;

bool IsAnagram(string a, string b)
{
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());

	if (a == b)
		return true;
	return false;
}

//bool IsAnagram1(string a, string b)
//{
//	sort(a.begin(), a.end());
//	sort(b.begin(), b.end());
//	if (a.size() != b.size())
//		return false;
//	for (auto i = 0; i < a.size(); i++)
//	{
//		if (a[i] != b[i])
//			return false;
//	}
//	return true;
//}
int main()
{
	string a = { "aabbcc" };
	string b = { "bwccaa" };

	if (IsAnagram(a, b) == true)
		cout << "true" << endl;
	else
		cout << "false" << endl;
}