[Hacker Rank, 해커랭크] Sherlock and Anagrams 문제 및 풀이( C# )

문제 링크: https://www.hackerrank.com/challenges/sherlock-and-anagrams/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps

Sherlock and Anagrams | HackerRank

이번 문제는 Dictionary와 Anagram의 원리를 이해하면 풀 수 있는 문제입니다.

Anagram은 단어의 순서를 바꿔 다른 단어를 만드는 놀이 입니다. 한글로는 '어구전철' 이라고 하는군요.

문제요약

난이도: Medium

• 문자열을 전부 해부하여 하위 문자열로 만든뒤,
• 하위 문자열들 중 Anagram이 되는 쌍이 몇 개인지 찾습니다.

---

Example>

• 문자열 s = "abba"
• 하위 문자열들 -> (1)[a,b,b,a], (2)[ab,bb,ba], (3)[abb, bba]
• Anagram 쌍들 -> [(a,a), (b,b)], [(ab, ba)], [(abb, bba)] 
• Anagram 의 쌍 갯수 -> 5개 

---

문제 풀이

이 문제를 크게 2가지로 먼저 나눠봤습니다.

 

1.  Anagram이 될 수 있는 모든 해부 경우의수 찾기
2. 모든 해부 경우의수를 돌아가며 Anagram쌍이 있는지 찾기

1번.

만약 abab가 있다면 모든 경우의 수를 찾을때 a,b,a,b, ab,ba,ab, aba,bab순으로 찾았습니다.

처음에는 한글자, 두번째 돌땐 두글자, 세번째 돌땐 세글자 순으로 for문을 돌렸습니다.

그리고 나온 모든 경우를 Dictionary에 저장하였습니다.

 

2번.

모든 경우의 수를 Dictionary에 넣은뒤, Dictionary를 배회하며

각각의 두 단어가 Anagram인지 확인하는 과정을 거쳤습니다.

 

Angram인지 확인하는 방법은 간단합니다.

두 개의 길이 26의 int배열을 만든뒤, 그 배열에 두 문자열의 아스키 코드값을 넣어줍니다.

그리고 두개의 배열을 for문을 돌리면서 두 수가 같은지 비교합니다.

비교했을때 전부 같으면 Anagram이고, 하나라도 다르면 Anagram이 아니게 됩니다.



이렇게 Dictionary를 돌며 두 쌍을 조사한뒤 같은 쌍의 갯수를 찾아 return해 줍니다.

 

실제 코드 구현 올려놓겠습니다~!

 

감사합니다 :)

using System.Collections.Generic;
using System;

class SherlockAndAnagrams
{
    static int sherlockAndAnagrams(string s)
    {
        return GetAnagramCount(GetAllCaseAnagram(s));
    }

    static Dictionary<int, List<string>> GetAllCaseAnagram(string s)
    {
        Dictionary<int, List<string>> anagramDictionary = new Dictionary<int, List<string>>();
        for (int i = 1; i <= s.Length - 1; ++i)
        {
            for (int j = 0; j < s.Length && j + i <= s.Length; j++)
            {
                string curString = "";

                for (int k = 0; k < i; ++k)
                    curString += s[j + k];

                int curStringLen = curString.Length;

                if (anagramDictionary.ContainsKey(curStringLen))
                    anagramDictionary[curStringLen].Add(curString);
                else
                    anagramDictionary.Add(curStringLen, new List<string> { curString });
            }
        }

        return anagramDictionary;
    }

    static int GetAnagramCount(Dictionary<int, List<string>> anagramDictionary)
    {
        int anagramCount = 0;
        foreach (var wordListDiv in anagramDictionary)
        {
            List<string> wordList = wordListDiv.Value;
            for (int i = 0; i < wordList.Count; ++i)
            {
                for (int j = i + 1; j < wordList.Count; ++j)
                {
                    if (IsAnagram(wordList[i], wordList[j]))
                        ++anagramCount;
                }
            }
        }

        return anagramCount;
    }

    static bool IsAnagram(string s1, string s2)
    {
        if (s1.Length != s2.Length)
            return false;

        int[] s1AlphaArr = new int[26];
        int[] s2AlphaArr = new int[26];

        for (int i = 0; i < s1.Length; ++i)
            ++s1AlphaArr[s1[i] - 'a'];

        for (int i = 0; i < s2.Length; ++i)
            ++s2AlphaArr[s2[i] - 'a'];

        for (int i = 0; i < 26; ++i)
        {
            if (s1AlphaArr[i] != s2AlphaArr[i])
                return false;
        }

        return true;
    }

    static void Main(string[] args)
    {
        int q = Convert.ToInt32(Console.ReadLine());

        for (int qItr = 0; qItr < q; qItr++)
        {
            string s = Console.ReadLine();
            int result = sherlockAndAnagrams(s);

            Console.WriteLine(result);
        }
    }
}