[백준] 스택 수열(1874)

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

스택의 후입선출 원리를 이용하여 오름차순 수열을 만들 수 있는지 판별하는 문제이다.

1부터 자연수를 증가시키면서 입력으로 주어진 숫자와 비교하여 증가시킨 자연수를 스택에 추가하거나 빼는 방식으로 풀면 된다.

문제 풀이 방법은 다음과 같다.

1. 현재 수열 값 ≥ 자연수인 경우
   현재 수열 값이 자연수보다 크거나 같을 때까지 자연수를 1씩 증가시키며 자연수를 스택에 push한다. 이후 수열을 출력하기 위해 마지막 1회만 pop한다.

   e.g. 현재 수열 값 = 4이면 스택에 1, 2, 3, 4를 push하고 마지막 값인 4만 pop하여 출력한다.
   (다음 순서를 위해 자연수는 5로 증가시킨다.)
   

2. 현재 수열 값 ＜ 자연수인 경우
   스택에서 pop하여 스택에 있는 값을 꺼낸다.

   만약 꺼낸 값이 현재 수열 값과 일치하지 않는다면 스택의 후입선출 원리를 이용하여 오름차순 수열을 표현할 수 없다. 따라서 NO를 출력하고 프로그램을 종료한다.

   • e.g. 1, 2, 5, 3, 4에서 1, 2, 5까지 스택에 push와 pop을 진행하여 표현할 수 있지만, 마지막으로 표현된 수가 5 이므로 후입선출 원리에 의해 3을 pop할 수 없다.

   만약 꺼낸 값이 현재 수열 값과 일치한다면 그대로 조건문을 빠져나와 다음 순서를 실행한다.

   • e.g. 1, 2, 5, 4, 3에서 1, 2, 5까지 스택에 push와 pop을 진행하여 표현한 다음, 마지막으로 표현된 수가 5 이므로 후입선출 원리에 의해 4를 pop할 수 있다.

Python

파이썬의 경우 문제풀이 코드는 다음과 같다.

N = int(input())
A = [0] * N

for i in range(N):
    A[i] = int(input())

stack = []
num = 1
result = True
answer = [] # 정답을 출력할 배열

# 1부터 num 값을 1씩 증가시키면서 입력값과 비교함
for i in range(N):
    su = A[i]

    # 현재 수열 값이 자연수보다 크거나 같은 경우
    # e.g. su == 4, num == 1
    if su >= num:
        while su >= num:
            # e.g. 1, 2, 3, 4
            stack.append(num) # num을 스택에 push
            num += 1 # num 1 증가
            answer.append('+')
        
        # e.g. 4를 pop
        stack.pop() # 한번만 pop을 진행해줘야 함
        answer.append('-')

    # 현재 수열 값이 자연수보다 작은 경우
    else:
        n = stack.pop() # 스택에서 값을 꺼낸 후
        
        # 현재 수열 값과 비교한다.

        # 꺼낸 값이 현재 수열 값이 아닌경우 스택의 후입선출 원리에 위배된다
        if n > su: 
            print("NO")
            result = False
            # 프로그램 종료
            break
        
        # 계속해서 스택 연산을 수행함
        else:
            answer.append('-')

if result:
    for i in answer:
        print(i)

Java

자바의 경우 문제풀이 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class P_1874 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }
        Stack<Integer> stack = new Stack<>();

        StringBuilder bf = new StringBuilder();
        int num = 1;
        boolean result = true;

        // 입력된 값에 대해 반복
        for (int i : A) {
            // 입력된 수열값이 자연수 num 보다 큰 경우
            // e.g. 4 >= 1인 경우 4를 만들기 위해 + + + + push
            if (i >= num) {
                while (i >= num) {
                    stack.push(num++);
                    bf.append("+\n");
                }
                // 마지막 1회만 - pop 진행
                stack.pop();
                bf.append("-\n");
            }

            // 입력된 수열값이 자연수 num 보다 작은 경우
            // e.g. 3 >= 5
            else {
                int next = stack.pop();

                // 꺼낸 next 값이 수열값과 일치하지 않는 경우
                if (i != next) {
                    System.out.println("NO");
                    result = false;
                    break;
                }
                
                // 꺼낸 next 값이 수열값과 일치하는 경우
                else {
                    bf.append("-\n");
                }
            }
        }
        if (result) System.out.println(bf);
    }
}