[C#] 1316번: 그룹 단어 체커

목차

---

백준 단계별로 풀어보기

25.08.25

6단계: 심화 1

1316번: 그룹 단어 체커

문제 링크 : https://www.acmicpc.net/problem/1316

 

문제 풀이

>> 문제를 풀기 위해 필요한 것

- 글자가 연속해서 나온 것인지 아닌지 구별하는 아이디어

: 이중 반복문을 활용하여 두 개의 글자를 서로 비교하고, 그 글자가 인접해있다면 넘어가기

 

>> 풀이

1. 첫째 줄에서 받은 개수 N만큼 반복하여 문자열을 받고 문자의 배열로 변환한다.
2. 이중 반복문을 통해 한 글자씩 서로 비교한다.
3. 비교했을 때 같은 글자라면 그 글자가 인접한지 확인하고 인접해있다면 continue로 넘긴다.
   • 처음에 조건을 (k - j == 1)로 뒀더니 연속해서 3번 이상 동일하게 나온 글자는 체크하지 못하는 경우가 있었다. 그래서 조건을 직전의 단어와 같은지 비교하는 것으로 변경했다.
4. 인접해있지 않다면 그룹 단어가 아니므로 첫째 줄에서 받은 개수 N개에서 1개 뺀다.
   • 처음에 'count--' 로 했더니 첫 반복문에서 반복할 횟수도 같이 줄어들어서 결과를 출력할 변수 'result'를 따로 만들어서 개수를 빼줬다.
5. 그룹 단어가 아니라면 더 반복해서 확인할 필요가 없기 때문에 break 해준다.
   • break 하나로는 이중 반복문을 빠져나갈 수 없기 때문에 bool 타입의 변수를 하나 생성하여 두번째 반복문도 빠져나가도록 해준다.

 

정답 코드

class Backjoon
{
    static void Main(string[] args)
    {
        int count = int.Parse(Console.ReadLine());
        int result = count;

        for (int i = 0; i < count; i++)
        {
            string input = Console.ReadLine();
            char[] arr = input.ToCharArray();

            bool isGroupWord = true;
            for (int j = 0; j < arr.Length; j++)
            {
                for (int k = j + 1; k < arr.Length; k++)
                {
                    if (arr[j] == arr[k])
                    {
                        if (arr[k - 1] == arr[k]) continue;
                        else
                        {
                            isGroupWord = false;
                            result--;
                            break;
                        }
                    }
                }
                if (!isGroupWord) break;
            }
        }
        Console.Write(result);
    }
}

 

※ 또 다른 아이디어

: 코드 자동완성으로 보게된 아이디어인데, 코드 전체가 이중 반복문으로 마무리돼서 시간복잡도상 훨씬 효율적인 코드이다.

 

>> 풀이

1. 첫째 줄에서 받은 개수 N만큼 반복하여 문자열을 받는다.
2. bool 타입의 배열을 알파벳 개수만큼의 크기로 선언한다.
3. 반복문을 통해 글자 하나씩 받고, 동일한 글자가 인접해있지 않다면 해당하는 알파벳 배열의 값을 true로 만든다.
4. 조건문에 해당하는 알파벳 배열의 값이 이미 true면 이전에 한번 나왔던 알파벳이면서 인접해있지 않은 것이므로 그룹 단어가 아니라는 말이 된다.
5. 명령문으로 개수를 카운팅하고 반복문을 종료한다.

 

>> 코드

class Backjoon
{
    static void Main(string[] args)
    {
        int count = int.Parse(Console.ReadLine());
        int result = count;

        for (int i = 0; i < count; i++)
        {
            string word = Console.ReadLine();
            bool[] alphabet = new bool[26];

            for (int j = 0; j < word.Length; j++)
            {
                if (j > 0 && word[j] != word[j - 1])
                {
                    if (alphabet[word[j] - 'a'])
                    {
                        result--;
                        break;
                    }
                    else
                    {
                        alphabet[word[j] - 'a'] = true;
                    }
                }
                else if (j == 0)
                {
                    alphabet[word[j] - 'a'] = true;
                }
            }
        }

        Console.Write(result);
    }
}