[백준] 1874번 스택 수열 [JAVA]

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

1874번: 스택 수열

---

     문제

 

     문제 풀이

• 전형적인 스택 문제이다. 자바의 경우 stack을 import해와서 사용하면 된다.
• 스택엔 push, pop, peek의 기능이 있다.(자바의 경우) push는 스택에 자료를 넣고, pop은 스택에서 자료를 뺀다. peek은 스택의 가장 나중에 들어간 자료를 보여만 주는 기능을 한다.
• NO가 나오는 경우는 언제일까?
  오름차순으로 pop이 될 수 있도록 스택을 하나 생성하고, 이를 오름차순으로 push를 모두 하였음에도 불구하고, 넣고 있는 스택의 size가 원하는 사이즈가 되지 않으면 EmptyStackException이 발생하게 되는데, 이를 예외처리를 통해 catch하여 NO가 출력되도록 하면 된다.
• 푼 방법
   오름차순으로 자료가 들어가있는 stack1, 비어있어 stack1의 자료를 push하고 입력되는 자료에 맞춰서 pop도 하는 stack, 이렇게 두개를 만든다. 그리고 stack.peek()을 통해 stack의 맨 위의 자료를 입력과 비교하여, 일치가 될 때까지 stack1의 자료를 push하고, stack의 자료를 pop을 적절하게 반복할 것이다.
  1. stack.peek()을 해서, 입력된 숫자가 일치하는지 안하는지를 검증한다.
  2. 일치하지 않을 땐, 입력된 숫자와 동일한 숫자가 stack에 들어갈 때까지, stack1의 자료를 stack에 push하고("+"도 출력), push된 자료는 stack1에선 pop하도록 한다.
  3. 일치하게 되면, stack.pop()을 하면 된다.("-"도 출력)
  1-3번의 반복

      주의했던 점

• stack의 size가 0일 때, stack을 peek하면 EmptyStackException이 발생하여 더 이상 검증을 하는 것이 불가능하다. 따라서 size가 0일 때만 peek을 하기 전에 push를 먼저하도록 순서를 바꾼다.
• 예외처리를 하면 입력을 다 하기도 전에 break가 걸려 끝까지 입력하는 것 자체가 불가능해지므로, 런타임 에러가 날 것을 우려했다. 따라서 이를 해결하기 위해, 일단 예외처리된 결과를 따로 배열리스트에 저장하고 끝까지 입력을 하도록 하였다.

---

        JAVA code

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

public class baekjoon1874 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> stack1 = new Stack<>();
        ArrayList<String> str = new ArrayList<>();
        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            int a = Integer.parseInt(br.readLine());
            arr[i] = a;
        }
        for (int i = N; i > 0; i--) {
            stack1.push(i);
        }

        for (int i = 0; i < N; i++) {
            int S = arr[i];
            try {
                if (stack.size() == 0) {
                    while (true) {
                        stack.push(stack1.peek());
                        stack1.pop();
                        str.add("+");
                        if (stack.peek() == S) {
                            str.add("-");
                            stack.pop();
                            break;
                        }
                    }
                } else {
                    while (true) {
                        if (stack.peek() == S) {
                            str.add("-");
                            stack.pop();
                            break;
                        }
                        stack.push(stack1.peek());
                        stack1.pop();
                        str.add("+");
                    }
                }
            } catch (EmptyStackException e) {
                str.add("NO");
                break;
            }
        }
        if (str.get(str.size() - 1) == "NO")
            System.out.println("NO");
        else
            for (String e : str) {
                System.out.println(e);
            }
    }
}