[3986] 좋은단어 (C#)

[문제]

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

3986번: 좋은 단어

 

가까운 같은 단어를 이었을 때 이은 선이 겹치지 않는 문자인지를 체크하는 문제.

 

[풀이컨셉]

문자를 이은 선이 겹치지 않으려면 가까운 문자끼리 대칭성을 가져야 한다. 대칭성이 없이 번갈아 나올 경우 첫번째 그림처럼 꼬이게 되고 다른 문자가 등장하더라도 가까운 문자끼리 대칭성을 이루면 두번째 그림처럼 선을 꼬이지 않게 그릴 수 있다. 따라서, 스택을 통해 문자를 저장하고 비교하는 문자가 스택의 마지막 요소와 일치할 때 꺼내면 꼬인 문자는 스택에 요소가 빠져나가지 못해 남아있게 되고, 대칭성을 이루는 문자열은 문자가 전부 빠져나가 검사를 마쳤을 때 아무 요소도 남지 않게 된다.

 

1. 검사할 문자열을 앞에서부터 체크한다.

2. 체크한 문자가 stack의 가장 마지막에 push한 peek와 다르면 push하고 같으면 pop한다.

3. 끝까지 검사를 마쳤을 때 남아있는 스택요소가 없다면 좋은단어+1, 아니면 꼬여있는 상태이므로 skip

4. 좋은 단어의 수 출력

 

[풀이]

int repeat = int.Parse(Console.ReadLine());
Stack<char> charStack = new Stack<char>();

int goodWordCount = 0;

            for (int i = 0; i < repeat; i++)
            {
                string targetString = Console.ReadLine();
                
                //이전 문자를 검사하면서 남아있는 문자 초기화
                charStack.Clear(); 

                for (int charIndex = 0; charIndex < targetString.Length; charIndex++)
                {
                	//비교할 문자가 없으면 push
                    if (charStack.Count.Equals(0))
                    {
                        charStack.Push(targetString[charIndex]);
                    }
                    //비교할 문자가 있을 때
                    else
                    {
                    	//스택의 마지막을 현재 문자와 비교
                        if (charStack.Peek().Equals(targetString[charIndex]))
                        {
                        	//쌍이 맞으면 꺼내기
                            charStack.Pop();
                        }
                        else
                        {
                        	//다르면 push
                            charStack.Push(targetString[charIndex]);
                        }
                    }
                }

                if (charStack.Count.Equals(0))
                {
                    goodWordCount++;
                }
            }

            Console.WriteLine($"{goodWordCount}");