[백준] C# 스택 수열 1874

파란색 : 풀면서 어려웠던 부분 or 고려해야 될 부분

빨간색 : 해결방법

초록색 : 느낀 점

문제

스택을 활용하는 문제이다.

풀이 : 내가 작성한 코드

            int length = int.Parse(Console.ReadLine());
            int[] nArray = new int[length];
            for (int i = 0; i < length; i++)
            {
                nArray[i] = int.Parse(Console.ReadLine());
            }

            int nCount = 0;
            int nIdx = 1;
            StringBuilder stringBuilder = new StringBuilder();
            Stack<int> stack = new Stack<int>();
            stack.Push(nIdx);
            stringBuilder.Append("+\n");

            while (nCount != length)
            {
                while (true)
                {
                    if (stack.Count != 0 && nArray[nCount] == stack.Peek())
                    {
                        int nPop = stack.Pop();
                        stringBuilder.Append("-\n");
                        nIdx = nPop > nIdx ? nPop : nIdx;
                        break;
                    }
                    else
                    {
                        nIdx++;
                        stack.Push(nIdx);
                        stringBuilder.Append("+\n");
                    }
                    if (nIdx > length)
                    {
                        Console.WriteLine("NO");
                        return;
                    }
                }

                nCount++;
            }
            Console.WriteLine(stringBuilder.ToString());

신경 써야 할부분은 스택에서 pop 된 후 바로 다음으로 나열되어야 하는 수가 peek에 있지 않으면 답은 "NO"가 출력되어야 한다.

처음에는 Idx로 push 할 때 +1해 주고 pop 할 때 -1을 했지만 그렇게 되면 pop 됐던 값이 다시 push 되기 때문에 nPop을 통해 방금 꺼낸 pop 된 값이 크면 nIdx값을 변경해줬다. 

 

예상된 수열로 불가능한 예시

 

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