백준1919번 애너그램 만들기(Anagram) C++로 구현해보기

 

```

백준1919번 애너그램 만들기(Anagram) C++로 구현해보기

```

 

이번 글을 통해 배워갈 내용

1.  애너그램
2.  아스키 코드를 배열로 다뤄보기

---

https://www.acmicpc.net/problem/1919

1919번: 애너그램 만들기

 

 

백준 1919번 애너그램 만들기는

난이도 쉬움 등급의 문제로서

 

영문 소문자 두개가 주어질때

두 소문자를 애너그램 관계로 표현 하려면 몇개의 문자를 지워야 하는지 계산해야 합니다.

 

---

그렇다면 애너그램 관계란 어떤 관계 일까요?

 

단어나 문장을 구성하는 문자의 순서를 바꾸어 다른 단어나 문장을 만들수 있을때 애너그램 관계에 있다고 합니다.

 

https://ko.wikipedia.org/wiki/%EC%96%B4%EA%B5%AC%EC%A0%84%EC%B2%A0

어구전철 - 위키백과, 우리 모두의 백과사전

 

한글로는 어구전철이라고 하는군요.

 

예를 들어

 

1.

ape(원숭이) 라는 단어를 pea(콩) 으로 바꿀때 문자의 순서만 변경하면 됩니다.

따라서 ape는 pea와 애너그램 관계에 있습니다.

 

2.

listen 이라는 단어를 silent로 바꾸면

 

두 단어 모두

l 한개

i 한개

s 한개

t 한개

e 한개

n 한개

t 한개

이고 그 외에 다른 문자는 없기 때문에 애너그램 관계에 있다고 합니다.

 

자 그럼 정의를 아셨으니

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

일단 해당 문제에서 두개의 단어가 필요하니

 

입력을 받습니다.

    string str1;
    string str2;
    
    cin >> str1;
    cin >> str2;

 

저는 함수를 좋아해서

입력 받은 스트링 값을 함수로 넣어줍니다.

cout << stepsRequiredToMakeAnagram(str1.c_str(), str2.c_str());

함수는

 

int stepsRequiredToMakeAnagram(const char Arr[], const char Arr2[])
{
	int lowCaseAlphabet[26] = { 0 };
	int counter = 0;
	for (int i = 0; Arr[i] != '\0'; i++)
	{
		int tempVal = Arr[i] - 'a';
		lowCaseAlphabet[tempVal]++;
	}
	for (int i = 0; Arr2[i] != '\0'; i++)
	{
		int tempVal = Arr2[i] - 'a';
		lowCaseAlphabet[tempVal]--;
	}
	for (int i = 0; i < 26; i++)
	{
		if (lowCaseAlphabet[i] < 0)
		{
			counter -= lowCaseAlphabet[i];
		}
		else
		{
			counter += lowCaseAlphabet[i];
		}
	}
	return counter;
}

 

위와 같이 두 값을 받아서

하나씩 분석을 합니다.

 

lowCaseAlphabet이라는 배열을 0으로 초기화 하고

첫번째 단어에서 a 부터 z 까지 문자가 나올때

lowCaseAlphabet 배열 안에 각 문자에 해당하는 위치 값을 추가해줍니다.

 

예) baac일 경우

lowCaseAlphabet 배열 안에 

a에 해당되는 값이 2

b에 해당되는 값이 1

c에 해당되는 값이 1

이 될겁니다

 

그리고 두번째 단어에 들어있는 a 부터 z 까지 문자가 나올때

lowCaseAlphabet 배열 안에 각 문자에 해당하는 위치 값을 빼줍니다.

 

예) 다시 baac 일 경우

lowCaseAlphabet 배열 안에

a에 해당되는 값이 2 - 2 = 0

b에 해당되는 값이 1 - 1 = 0

c에 해당되는 값이 1 - 1 = 0

이 될겁니다

 

두 단어는 애너그램이기 때문에 더 연산을 안해도 됩니다.

 

그렇다면 애너그램이 아닌경우

 

예)

codemaster

cppmaster의 경우

 

첫번째 단어에 o가 한개, d가 한개, e가 한개 더 많습니다.

두번째 단어에 p가 두개 더 많습니다

 

결과는

첫번째 단어에 3개, 두번째 단어에 2개를 빼야 될것이고

 

그 작업을 함수 마지막 부분에서

lowCaseAlphabet을 돌면서 counter에 더해주는 작업을 하면서 해줍니다.

 

counter 값을 리턴해주고 출력하면서 종료되고

 

전체 함수는 다음과 같습니다

 

 

#include <iostream>

using namespace std;

int stepsRequiredToMakeAnagram(const char Arr[], const char Arr2[])
{
	int lowCaseAlphabet[26] = { 0 };
	int counter = 0;
	for (int i = 0; Arr[i] != '\0'; i++)
	{
		int tempVal = Arr[i] - 'a';
		lowCaseAlphabet[tempVal]++;
	}
	for (int i = 0; Arr2[i] != '\0'; i++)
	{
		int tempVal = Arr2[i] - 'a';
		lowCaseAlphabet[tempVal]--;
	}
	for (int i = 0; i < 26; i++)
	{
		if (lowCaseAlphabet[i] < 0)
		{
			counter -= lowCaseAlphabet[i];
		}
		else
		{
			counter += lowCaseAlphabet[i];
		}
	}
	return counter;
}

int main()
{
    string str1;
    string str2;
    
    cin >> str1;
    cin >> str2;
    
    cout << stepsRequiredToMakeAnagram(str1.c_str(), str2.c_str());

    return 0;
}

 

1.

입력

abcd

abbbbb

결과

6

 

2.

 

 

입력

codemaster
cppmaster

결과
5

통과했습니다

 

복잡도는 O(n) 이기 떄문에 시간은 매우 빠릅니다.

 

---

 

---

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩하시길 바랍니다 ~ :)

 

참조 및 인용

C++ Primer

 

---