[BAEKJOON] 백준 1544: 사이클 단어 (C#)

문제 링크

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

 

 

문제

사이클 단어는 어떤 단어를 원형 모양으로 차례대로 쓴 것이다. 따라서, 어떤 단어를 이렇게 쓴 후에 임의의 단어를 고른다. 그 후에 시계방향으로 차례대로 읽으면 그 것이 단어가 된다. 만약에 단어 A와 단어 B가 있을 때, 단어 B를 원형으로 써서, 단어 A와 같이 읽을 수 있으면, 두 단어는 같은 단어이다. 따라서, picture와 turepic은 같은 단어다.

N개의 단어가 주어졌을 때, 서로 다른 단어가 총 몇 개인지 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 단어가 한 줄에 하나씩 주어진다. 단어는 영어 소문자로만 이루어져 있다. N은 50보다 작거나 같은 자연수이며, 단어의 길이는 최대 50이다.

 

 

출력

첫째 줄에 서로 다른 단어가 몇 개인지 출력한다.

 

 

 

통과한 답안

namespace _1544
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            HashSet<string> Words = new HashSet<string>();

            for (int i = 0; i < N; i++)
            {
                string word = Console.ReadLine();
                bool isNewWord = true;

                for (int j = 0; j < word.Length; j++)
                {
                    string rotatedWord = word.Substring(j) + word.Substring(0, j);

                    if (Words.Contains(rotatedWord))
                    {
                        isNewWord = false;
                        break;
                    }
                }

                if (isNewWord)
                {
                    Words.Add(word);
                }
            }

            Console.WriteLine(Words.Count);
        }
    }
}

 

N개의 문자들이 주어졌을 경우 서로 다른 문자의 개수를 구하는 문제이다.

단 이 문제에서는 문자가 적혀있는 방식이 원형으로 적혀있기 때문에

문자를 읽기 시작하는 위치에 따라서 달라보이는 문자도 같은 문자로 취급하는 특징이 있다.

예를 들어서 picture는 icturep, cturepi, turepic, urepict, repictu, epictur로 읽을 수 있으며,

이 문자들은 모두 하나의 문자로 취급한다.

 

처음에는 문자를 입력 받은 후에 그 문자를 1번 더 적어서 길이가 2배인 문자를 만들고

(예를 들어 picture를 입력 받는다면 picturepicture를 만들고)

새롭게 입력받은 문자가 이 문자에 포함되는지 확인하도록 구현하였으나,

예제 3번과 같이 같은 문자를 반복하는 경우에는 정확하게 작동하지 않는 것을 확인하였다.

아래는 오답코드

namespace _1544
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            HashSet<string> Words = new HashSet<string>();

            for (int i = 0; i < N; i++)
            {
                string word = Console.ReadLine();
                string doubleWord = word + word;

                bool isNewWord = true;
                foreach (string existWord in Words)
                {
                    if (doubleWord.Contains(existWord))
                    {
                        isNewWord = false;
                        break;
                    }
                }

                if (isNewWord)
                {
                    Words.Add(word);
                }
            }

            Console.WriteLine(Words.Count);
        }
    }
}

 

이를 해결하기 위해서 입력받은 문자에서 한칸씩 오른쪽으로 이동된 모든 문자들에 대해서

지금 저장된 문자와 같은지 확인하도록 수정하였다.