[Baekjoon/C++] 1919번 - 애너그램 만들기

[백준] Baekjoon Online Judge

문제로 이동

 

문제

두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다. 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs의 각 문자들의 순서를 잘 바꾸면 succor이 되기 때문이다.

한 편, dared와 bread는 서로 애너그램 관계에 있지 않다. 하지만 dared에서 맨 앞의 d를 제거하고, bread에서 제일 앞의 b를 제거하면, ared와 read라는 서로 애너그램 관계에 있는 단어가 남게 된다.

두 개의 영어 단어가 주어졌을 때, 두 단어가 서로 애너그램 관계에 있도록 만들기 위해서 제거해야 하는 최소 개수의 문자 수를 구하는 프로그램을 작성하시오. 문자를 제거할 때에는 아무 위치에 있는 문자든지 제거할 수 있다.

 

입력

첫째 줄과 둘째 줄에 영어 단어가 소문자로 주어진다. 각각의 길이는 1,000자를 넘지 않으며, 적어도 한 글자로 이루어진 단어가 주어진다.

 

출력

첫째 줄에 답을 출력한다.

 

---

예제 입력	예제 출력
aabbcc xxyybb	8

---

풀이

#include <iostream>
using namespace std;

int main() {
	string a, b; // 두 영어 단어

	cin >> a >> b;

	int count = 0; // 두 영어 단어에 모두 포함되는 문자의 수

	// 두 영어 단어에 모두 포함되는 문자의 수 구하기
	for (int i = 0; i < a.length(); i++) {
		for (int j = 0; j < b.length(); j++) {
			if (a[i] == b[j]) {
				b[j] = 'A';
				count++;
				break;
			}
		}
	}

	// 출력
	printf("%d\n", (a.length() - count) + (b.length() - count));

	return 0;
}

두 영어 단어가 애너그램 관계가 되기 위해서는 서로에게 없는 문자를 버려야 한다. 그렇기에 두 단어 모두에 포함되는 문자의 수(count)를 센 다음 그 수를 각 영어 단어의 길이에 뺐다. 이때 count를 구할 때 같은 문자를 또 세는 것을 막기 위해 이미 서로 같은 문자를 가지고 있다고 판단되는 문자를 'A'로 바꿨다.