[백준저지] 1874번 : 스택 수열

www.acmicpc.net/problem/1874

1874번: 스택 수열

1. 문제

임의의 수열이 주어졌을 때 스택을 이용해서 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop을 해야하는지 출력하는 문제.

 

입)

8

4

3

6

8

7

5

2

1

 

출)

+

+

+

+

-

-

+

+

-

+

+

-

-

-

-

-

2. 풀이

import java.io.*;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void calculate(int[] numArr) {
        int crtnNum = 0;
        StringBuffer sb = new StringBuffer();
        Stack<Integer> stack = new Stack<>();
        for (int num : numArr) {
        	// 입력값이 기준값보다 큰 경우
            if (num > crtnNum) {
        		// 같아질 때까지 ++하면서 스택에 push
                while (num > crtnNum) {
                    stack.push(++crtnNum);
                    sb.append("+\n");
                }
                stack.pop();
                sb.append("-\n");
            } else {
            	// 스택에 있는 제일 큰 값보다 작은 경우
                // NO
                if (stack.peek() != num) {
                    System.out.println("NO");
                    return;
                }
                // 같은 경우 pop
                stack.pop();
                sb.append("-\n");
            }
        }
        System.out.println(sb.toString());
    }
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        // 수열의 길이를 입력받고
        int cnt = sc.nextInt();
        // 그 길이에 맞게 array 생성
        int[] numArr = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            numArr[i] = sc.nextInt();
        }
        calculate(numArr);
    }
}

 기준값을 하나 두고 입력값이랑 비교해서 입력값이 기준값보다 크면 같아질 때까지 기준값을 ++하면서 스택에 push해주고 같아진 경우 그 값을 pop한다. 

 기준값보다 작은 경우는 불가하므로 종료. 같은 경우에는 pop을 한다.