[ BOJ/C# ] 1874 스택 수열

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

1874번: 스택 수열

문제의 이해와 풀이과정에서 많이 헷갈렸다. 그래서 주석으로 한 단계씩 최대한 풀어가며 설명해두었다.

 

[Stack에는 1부터 오름차순으로 정수를 넣는다. ]

 

풀이 과정

1. 주어진 정수를 마지막 정수가 올 때까지 반복한다. 

2. Stack의 최댓값(혹은 가장 뒤의 값)_Stack.Max 혹은 Stack.Peek 상관없다(오름차순이기 때문)_이

    목표 정수보다 작다면 Stack에 정수 push

3. 목표 정수보다 크다면 pop, index 그대로(목표는 달성하지 못했기 때문)

4. 목표 정수와 같다면 pop, index 증가(다음 목표 정수로)

 

예외)

Max와 Peek를 사용하여 조건문을 작성하였기 때문에, 값이 존재하지 않는다면 에러가 뜬다. 

따라서 다음 정수를 넣어준다. 

 

중단 조건)

목표 정수가 이미 pop되었을 경우. 

이를 판별하기 위하여 List를 만들어 pop된 정수들을 저장하여 List.Contains로 확인한다. 

있다면 StringBuilder를 초기화하고 NO 출력

 

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

namespace _1874
{
    class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            StringBuilder sb = new StringBuilder();


            int length = int.Parse(sr.ReadLine());      //첫 줄은 수열의 길이
            int[] arr = new int[length];                //길이만큼 배열의 크기 설정

            for (int i = 0; i < length; i++)            //수열을 이루는 정수들 저장
            {
                arr[i] = int.Parse(sr.ReadLine());
            }

            //stack에 1부터 수열의 길이 정수까지 저장
            int index = 0;
            Stack<int> stack = new Stack<int>();

            //초기 세팅
            int j = 0;

            //pop한 정수 저장_중복 정수 판별하기 위해
            List<int> pop = new List<int>();

            //마지막 주어진 정수까지 반복
            while(index < length)
            {
                //진행이 불가능한 경우_목표 정수가 이미 pop 되었을 경우
                if (pop.Contains(arr[index]))
                {
                    sb.Clear();
                    sb.AppendLine("NO");
                    break;
                }
                //stack이 비어있지만 진행이 가능한 경우
                if (stack.Count == 0)
                {
                    j++;
                    stack.Push(j);
                    sb.AppendLine("+");
                }

                if (stack.Peek() < arr[index])   //1. 최댓값(가장 뒤의 값)이 목표 정수보다 작으면 push (1, 2, 3, ... )
                {
                    j++;
                    stack.Push(j);
                    sb.AppendLine("+");
                }
                else if (stack.Peek() == arr[index])   //2. 같으면 pop
                {
                    pop.Add(stack.Pop());
                    sb.AppendLine("-");
                    index++;
                }
                else   //3. 최댓값이 목표 정수보다 크다면
                {
                    pop.Add(stack.Pop());
                    sb.AppendLine("-");
                }
            }
            sw.WriteLine(sb);
            sr.Close();
            sw.Flush();
            sw.Close();
        }
    }
}

+어떤 분이 올려주신 반례 모음!!

https://www.acmicpc.net/board/view/107419

글 읽기 - 반례 모음