[스택] 백준 1874번 스택 수열(Java)

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

1874번: 스택 수열

📚 문제

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

📖 문제 해설

	스택	배열	출력
push 1	{1}	{}	+
push 2	{1, 2}	{}	+
push 3	{1, 2, 3}	{}	+
push 4	{1, 2, 3, 4}	{}	+
pop 4	{1, 2, 3}	{4}	-
pop 3	{1, 2}	{4, 3}	-
push 5	{1, 2, 5}	{4, 3}	+
push 6	{1, 2, 5, 6}	{4, 3}	+
pop 6	{1, 2, 5}	{4, 3, 6}	-
push 7	{1, 2, 5, 7}	{4, 3, 6}	+
push 8	{1, 2, 5, 7, 8}	{4, 3, 6}	+
pop 8	{1, 2, 5, 7}	{4, 3, 6, 8}	-
pop 7	{1, 2, 5}	{4, 3, 6, 8, 7}	-
pop 5	{1, 2}	{4, 3, 6, 8, 7, 5}	-
pop 2	{1}	{4, 3, 6, 8, 7, 5, 2}	-
pop 1	{}	{4, 3, 6, 8, 7, 5, 2, 1}	-

	스택	배열	출력
push 1	{1}	{}	+
pop 1	{}	{1}	-
push 2	{2}	{1}	+
pop 2	{}	{1, 2}	-
push 3	{3}	{1, 2}	+
push 4	{3, 4}	{1, 2}	+
push 5	{3, 4, 5}	{1, 2}	+
pop 5	{3, 4}	{1, 2, 5}	-

📝 문제 해결

1부터 n까지 반복문을 돌리며 오름차순으로 stack에 push 해준다.

스택이 비어있지 않을 때,

• 스택의 가장 위의 값이 배열의 해당 인덱스값과 같은 경우 스택에서 제거해주고 배열의 다음 인덱스로 넘어간다.
• 반면 값이 같지 않으면 원하는 숫자가 나올때까지 push 해준다.

반복을 마쳤을 때 스택이 비어있지 않으면 NO 출력해준다.

💻 코드

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

public class BOJ1874{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        
        Stack<Integer> stack = new Stack<Integer>();
        
        int n = sc.nextInt();
        int[] list = new int[n];
        for(int i=0; i<n; i++) list[i] = sc.nextInt();
        
        int index = 0;
        
        for(int i=1; i<=n; i++){
            stack.push(i);
            sb.append('+').append('\n');
            
            while(!stack.isEmpty()){
                if(stack.peek() == list[index]){
                    stack.pop();
                    sb.append('-').append('\n');
                    index++;
                }else{
                    break;
                }
            }
        }
        
        if(!stack.isEmpty()) System.out.println("NO");
        else System.out.println(sb);
    }
}