2024. 6. 3. 15:24ㆍIT/BaekJoon
문제 링크
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의 기본적인 기능을 활용해보는 문제였다고 생각한다.
'IT > BaekJoon' 카테고리의 다른 글
[BAEKJOON] 백준 3595: 맥주 냉장고 (C#) (0) | 2024.06.03 |
---|---|
[BAEKJOON] 백준 3622: 어떤 호박의 할로윈 여행 (C#) (0) | 2024.06.03 |
[BAEKJOON] 백준 1614: 영식이의 손가락 (C#) (0) | 2024.06.02 |
[BAEKJOON] 백준 1560: 비숍 (C#) (1) | 2024.06.02 |
[BAEKJOON] 백준 1449: 수리공 항승 (C#) (0) | 2024.06.02 |