[백준] 1874 스택 수열(c#)

문제

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

1874번: 스택 수열

스택에 1부터 n까지 수를 순서대로 넣고 빼면서 제시된 수(ex. 4 3 6 8 7 5 2 1)을 만들면 되는 것이다. 안만들어지면 "NO"를 출력하면 된다.

 

 

코드

using System;
using System.Text;
using System.Collections.Generic;

namespace baekjoon
{
    class Algorithm
    {
        static void Main(string[] str)
        {
            int cnt = Convert.ToInt32(Console.ReadLine()); // "8" -> 8
            Stack<int> stack = new Stack<int>();
            StringBuilder sb = new StringBuilder();
            int num = 1;
            bool YN = true;
            
            for(int i = 0; i < cnt; i++)
            {
                int target = Convert.ToInt32(Console.ReadLine());
                
                if(!stack.Contains(target))
                {
                    for(int j = num; j <= target; j++) 
                    {
                        stack.Push(j);
                        sb.AppendLine("+");
                        num = j+1;
                    }
                }
                
                if(stack.Contains(target) && stack.Peek() == target)
                {
                    stack.Pop();
                    sb.AppendLine("-");
                }
                else 
                {
                    YN = false;
                }
            }
            if(YN) 
            {
               Console.WriteLine(sb); 
            }
            else
            {
                Console.WriteLine("NO");
            }
            
            stack.Clear();
        }
    }
}

 

고민

stack에 1, 2, 3, 4..까지 넣었는데 어? 4가 제시됐네? 4를 빼고 +를 출력한다.

이런식으로 접근을 했는데, 이러니까 처음 숫자는 판별하기 쉬우나 두번째 숫자부터는 if문이 너무 많이 생기고 로직도 생각하기에 복잡해졌다. 다른 풀이를 찾아보니 Contain을 적극적으로 활용했다.

어라 이미지 실수. stack.Peek() == target입니다.

어차피 tartget이 있는데, 최상단(Peek)에 위치하면 원하는 조합을 만들 수 없으니 단호하게 NO를 출력하도록했다.

 

이런 로직은 어떻게 생각하는거지 다들? 규칙성 찾기가 너무 어렵다. 문제 푸는데 30분 걸렸다. 슬프다.