[백준/C++] 1919 : 애너그램 만들기

   문제   

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

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

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

 

   입력   

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

 

   출력   

첫째 줄에 답을 출력한다.

 

   예제   

---

   코드   

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int tmp[26] = {0}, ans = 0;
	string a, b;
	cin >> a >> b;

	for (auto c : a) tmp[c - 'a']++;
	for (auto c : b) tmp[c - 'a']--;

	for (int i = 0; i < 26; i++) {
		//ans += tmp2[i] > tmp1[i] ? tmp2[i] - tmp1[i] : tmp1[i] - tmp2[i];
        ans += abs(tmp[i]);
    }
	cout << ans;
}

변수 a, b에 두 문자열을 각각 저장한다.

먼저 반복문에서 첫 번째 문자열 a를 돌면서 각 알파벳의 빈도수를 계산한 후 tmp에 더해준다.

두 번째 문자열 b에서 계산한 알파벳 빈도수는 tmp에서 빼준다.

한 문자열에서 다른 문자열에 없는 알파벳을 갖고 있거나, 같은 알파벳을 갖고 있지만 그 빈도수가 다르다면 tmp[해당 알파벳]이 0이 아닌 값을 갖고있을 것이다.

그 차이만큼 문자를 제거해주어야 하기때문에 배열 tmp를 돌면서 차이의 절댓값을 변수 ans에 더해준다.

 

이 문제는 11328번 Strfry와 비슷하다.

여기서도 나는 처음에 각 문자열의 알파벳 빈도수를 따로 저장하기 위해 배열 tmp1과 tmp2를 모두 사용했지만 배열 1개만 사용해서 푸는 코드로 수정해보았다. 

그리고 절댓값 함수인 abs()를 몰라서 삼항 연산자를 이용했지만 다음부터는 기억두고 사용해봐야겠다!

 

문제 출처: 1919번: 애너그램 만들기 (acmicpc.net)

1919번: 애너그램 만들기