[코딩테스트] BOJ 1874 - 스택 수열 (성공)

 

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

1874번: 스택 수열

 

 

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

 

 

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

 

 

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

 

 

예제 입력 1

8
4
3
6
8
7
5
2
1

 

예제 출력 1

+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

 

 

예제 입력 2

5
1
2
5
3
4

 

예제 출력 2

NO

 

 

힌트

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

 

 

알고리즘 분류

• 자료 구조
• 스택

 

 

풀이

처음 이 문제를 풀때 무슨 말인지 몰랐다. 

주어진 수열을 스택을 이용해서 등차수열로 만들 수 있는지를 묻는건가 싶었다. (혼자서 문제를 만들어내서 풀고 있었다)

 

문제를 다시 읽어보니 1부터 n까지의 수로 주어진 수열을 만들 수 있는지를 물어보는 것이였다. 

문제를 제대로 읽지 않고 무작정 문제를 풀었고 잘못된 풀이를 떠올린 것 같다. 

 

문제를 이해하고 어떻게 구현을 할지 손으로 정리를 해봤다. 

1. stack.Peek()가 수열[j]와 일치하면 -> stack.Pop()을 한다. '-'을 출력한다. j++
2. 1부터 n까지 stack에 Push한다. '+'를 출력한다. 
3. 넣은 숫자(stack.Peek())가 수열[j]와 일치하면 -> stack.Pop()을 한다. '-'을 출력한다. j++

 

 

코드

using System.Text;

namespace 스택
{
    internal class BOJ1874_스택_수열
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            StringBuilder sb = new StringBuilder();

            int n = int.Parse(sr.ReadLine());
            int[] intArray = new int[n];
            for(int i = 0; i < n; i++)
            {
                intArray[i] = int.Parse(sr.ReadLine());
            }

            Stack<int> stack = new Stack<int>();
            int j = 0;
            bool isSuccess = false;
            for(int i = 1; i < n+1; i++)
            {
                while(stack.Count != 0 && stack.Peek() == intArray[j])
                {
                    stack.Pop();
                    sb.Append("-");
                    j++;

                    if(stack.Count == 0)
                    {
                        isSuccess = true;
                        break;
                    }
                }

                stack.Push(i);
                sb.Append("+");

                while(stack.Peek() == intArray[j])
                {
                    stack.Pop();
                    sb.Append("-");
                    j++;

                    if(stack.Count == 0)
                    {
                        isSuccess = true;
                        break;
                    }
                }
            }

            // 스택에 원소가 남아있으면 
            if (stack.Count != 0)
            {
                sw.WriteLine("NO");
            }
            // 스택에 원소가 남아있지 않으면, isSuccess가 true이면 
            else if (stack.Count == 0 && isSuccess)
            {
                foreach (char c in sb.ToString())
                {
                    sw.WriteLine(c);
                }
            }

            sw.Close();
            sr.Close();
        }
    }
}

 

 

복습1 풀이 (6/4)

문제 = 스택에 1 ~ n까지 수를 넣는다. 
임의의 수열이 주어졌을 때, 스택을 이용해 그 수열을 만들 수 있다면 어떤 순서로 push, pop을 해야하는지 계산 

입력
1. n (1 <= n <= 100,000)
2 ~ n. 1이상 n이하 정수 

 

출력
입력으로 주어진 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력 
(push 연산은 +, pop 연산은 -로 표현, 불가능한 경우 NO 출력)


풀이

주어진 수열을 스택에 1부터 n까지 넣고 빼면서 만들 수 있는지, 만들 수 있다면 push, pop 기호를 출력하고, 만들 수 없다면 NO를 출력하면 된다. 

 

코드로는 어떻게 짜면 좋을지 생각해봤다. 
0. 1부터 n까지 반복
1. 스택의 Peek가 비어있다면(스택에 길이가 0이면), 스택에 i를 넣는다. 
2. 스택의 Peek가 nums[index]와 같다면, 스택을 pop한다 (-), index++ 
2. 스택의 Peek가 nums[index]와 다르다면, 계속해서 스택에 i를 넣는다. (+)

이렇게 정리는 했지만.. 잘 모르겠다. 그냥 코드 바로 짜보자. 

 

 

코드1 - 정답

using System.Text;

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

        Stack<int> stack = new Stack<int>();

        int n = int.Parse(sr.ReadLine());
        int[] nums = new int[n];
        int index = 0; 

        for(int i = 0; i < nums.Length; i++)
            nums[i] = int.Parse(sr.ReadLine());

        int num = 1; 
        bool isSuccess = true;
        while (true)
        {
            if(stack.Count > 0 && stack.Peek() == nums[index])
            {
                stack.Pop();
                sb.AppendLine("-");
                index++;
                if(index >= n) break;
                continue;
            }

            if(num > n)
            {
                isSuccess = false;
                break;
            }
            stack.Push(num++);
            sb.AppendLine("+");
        }

        if(!isSuccess) 
            sw.WriteLine("NO");
        else
            sw.WriteLine(sb.ToString());

        sr.Close();
        sw.Close();
        sb.Clear();
    }
}

 

 

배운점

풀이 과정이 좀 이상하더라도 일단 적은대로 짜보자. 짜보고 안되면 다른 풀이를 생각해보면 된다.