[BAEKJOON] 백준 3778: 애너그램 거리 (C#)

문제 링크

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

 

 

문제

만약 단어 A의 알파벳 순서를 바꿔서 단어 B를 만들 수 있다면, 두 단어는 애너그램이라고 한다. 예를 들어, occurs는 succor의 애너그램이지만, dear는 dared의 애너그램이 아니다. 영어에서 가장 유명한 애너그램은 dog와 god이다.

두 단어의 애너그램 거리란, 두 단어가 애너그램이 되기 위해서 지워야하는 단어의 최소 개수이다. 예를 들어, sleep과 leap이 주어졌다면, sleep에서 2개, leap에서 1개를 지운다면 두 단어는 애너그램 관계가 된다. 따라서, sleep과 leap의 애너그램 거리는 3이다. 서로 공통된 알파벳이 없는 dog와 cat같은 경우에는 모든 단어를 지워야 하기 때문에, 애너그램 거리가 6이다.

두 단어가 주어졌을 때, 두 단어의 애너그램 거리를 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 테스트 케이스의 개수 N이 주어진다. N은 60,000보다 작거나 같은 자연수이다. 각 테스트 케이스는 두 줄로 이루어져 있고, 한 줄에 단어가 하나씩 주어진다.

단어의 길이는 0일 수도 있고, 알파벳 소문자로만 이루어져 있다. 단어는 실제로 영어 사전에 있는 단어만 주어지며, 영어 사전에서 가장 긴 단어는 pneumonoultramicroscopicsilicovolcanoconiosis이다.

 

출력

각 테스트 케이스에 대해서 케이스 번호와 입력으로 주어진 두 단어의 애너그램 거리를 출력한다.

 

 

 

통과한 답안

namespace _3778
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            for (int i = 0; i < N; i++)
            {
                string word1 = Console.ReadLine();
                string word2 = Console.ReadLine();
                Dictionary<char, int> dict1 = new Dictionary<char, int>();
                Dictionary<char, int> dict2 = new Dictionary<char, int>();

                for (int j = 0; j < word1.Length; j++)
                {
                    if (dict1.ContainsKey(word1[j]))
                    {
                        dict1[word1[j]]++;
                    }
                    else
                    {
                        dict1.Add(word1[j], 1);
                    }
                }

                for (int j = 0; j < word2.Length; j++)
                {
                    if (dict2.ContainsKey(word2[j]))
                    {
                        dict2[word2[j]]++;
                    }
                    else
                    {
                        dict2.Add(word2[j], 1);
                    }
                }

                int cnt = 0;

                foreach (var item in dict1.Keys)
                {
                    if (dict2.ContainsKey(item))
                    {
                        cnt += Math.Abs(dict1[item] - dict2[item]);
                    }
                    else
                    {
                        cnt += Math.Abs(dict1[item]);
                    }
                }

                foreach (var item in dict2.Keys)
                {
                    if (!dict1.ContainsKey(item))
                    {
                        cnt += Math.Abs(dict2[item]);
                    }
                }

                Console.WriteLine($"Case #{i + 1}: {cnt}");
            }
        }
    }
}

 

두 단어가 주어졌을 때, 두 단어에서 다른 알파벳의 개수를 구하는 문제이다.

이를 해결하기 위해서 각 단어에 대한 Dictionary를 생성하고,

알파벳의 개수를 저장하도록 구현하였다.

 

이후에 두 Dictionary를 순회하면서

같은 단어가 있다면 그 차이를 저장하고 다른 단어라면 그 수를 저장하도록 구현하였다.

 

Dictionary의 기본적인 기능을 활용해보는 문제였다고 생각한다.