1874.스택수열

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

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

풀이

알고리즘 흐름

1. 입력 받기
2. 입력받은 값을 PUSH 하기
3. 원하는 숫자일때 POP하기
4. 만약 해당숫자가 못나온다면 NO 출력
5. 모두 출력되었다면 sb에 저장된 값을 출력

• 이때 스택에 수를 넣을때는 반드시 오름차순으로 들어간다.

만약에 입력값이 8이라면
1 2 3 4 5 6 7 8 이렇게 PUSH가 일어날것이다.
그리고 꺼내야될 값이 된다면 해당 값을POP할것이다.

예를 들어보자. 만약 입력이 아래와 같다고 생각해보자.

5
4
2
3
1
5

첫번째의 5는 갯수N이므로 그뒤에 5개가 나올것을 알려준다. 생략하고 다음 숫자를 보자

4 ! 자 그럼 4를 꺼낼려면 어떻게 해야할까? 일단 4개를 PUSH해야할것이다.

즉 스택을 본다면 다음과 같다.

STACK - 1
STACK - 1 2
STACK - 1 2 3
STACK - 1 2 3 4

4가 나왔다. 그럼 문제에서 원하는 4를 찾았으므로 4를 POP한다. 그럼 다음과 같이 된다.
STACK - 1 2 3
다음으로 찾을 숫자는 2이다. 2를 찾으려고 보니 3이 TOP에 있다. 그럼 POP 연산으로 없애준다.
STACK - 1 2
그럼 2가 나왔다. 문제에서 원하는 값을 찾았으니 2를 POP 해준다.
STACK - 1
다음으로 찾을숫자는 3이다. 3을 찾아야하는데 우리가 4까지 PUSH를 했으므로 오름차순으로 PUSH되려면 다음으로 PUSH되는 값은 5이다.
STACK - 1 5
아무리 여기서 5 6 7 8 추가가 되어도 찾으려는 3은 찾을수없을것이다.

이렇게 되었을때 출력은 "NO"가 출력된다.

코드

import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

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

        int n = sc.nextInt();

        int start = 0;

        for(int i=0; i<n; i++){

            int value = sc.nextInt();

            if(value > start){

                for(int j=start+1; j<=value; j++){
                    stack.push(j);
                    sb.append('+').append('\n');
                }
                start = value;
            } else if (stack.peek() != value) {
                System.out.println("NO");
                return;
            }

            stack.pop();
            sb.append('-').append('\n');
        }

        sc.close();

        System.out.println(sb);
    }
}