[백준] 1919 애너그램 만들기

문제 설명

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

1919번: 애너그램 만들기

두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다

 

두 영어 단어가 주어졌을 때, 두 단어가 서로 애너그램 관계에 있도록 만들기 위해서 제거해야 하는 최소 개수의 문자 수를 구하기

 

문제 풀이법

처음에 문제를 잘못읽고 다른 방향으로 문제를 풀려 했었다

"철자의 순서를 뒤바꾸어 같아질 수 있다" 라는 말을 example <-> elpmaxe 이렇게 데칼코마니와 같아져야한다는 말인 줄 알았다

알고보니 순서를 아무렇게나 바꿔도 되는 것이었다

 

따라서 애너그램의 관계가 되기 위해서는 같은 알파벳만 사용하면 된다

이 문제는 [백준 11328 Strfry] 문제와 매우 유사하다

 

문자열을 입력받은 후, 알파벳의 개수를 담을 배열을 선언해 문자열1에서는 +1을 하면서 알파벳이 얼마나 담겼는지 저장하고,

문자열2에서는 -1을 하면서 문자열1에서 담긴 알파벳을 빼도록 한다

 

문자열 1과 문자열 2가 서로 같은 알파벳과 그 개수도 동일하다면 배열의 값은 0일 것이다

하지만 문제에서 애너그램을 만들기 위해 제거해야 하는 문자 수를 구해야 했으니, 배열의 값이 0이 아닌 수를 모두 더하면 구할 수 있다

문자열2를 for문 돌면서 음수 값을 가진 수도 있을 테니 절대값 함수인 abs를 활용하여 구한다

 

소스 코드

#include <iostream>
#include <cstdlib>
using namespace std;

int main()
{
    string str1, str2;
    
    getline(cin, str1);
    getline(cin, str2);
    
    int arr[26] = { 0 };

    for (int i = 0; i < str1.size(); i++)
        arr[str1[i] - 'a']++;
    for (int i = 0; i < str2.size(); i++)
        arr[str2[i] - 'a']--;

    int cnt = 0;
    for (int i = 0; i < 26; i++)
    {
        if (arr[i] != 0)
        {   
            cnt += abs(arr[i]);
        }
    }
    printf("%d\n",cnt);
    return 0;
}