백준 1874번 : 스택 수열 자바

🧫 문제 분석

✔️ 출처

스택 수열 실버 2

 

📖 문제

 

1~N까지의 숫자들이 오름차순으로 스택에 push될 수 있고,

입력된 수열, 여기서는

[4 3 6 8 7 5 2 1] 이라는 수열을 만들기 위해 

스택이 해야하는 연산을 출력하는 문제이다.

push : + 

pop : -

 

우선 먼저 수열의 맨 처음인 4를 놓기 위해서는 

1~4까지 스택에 push 후 1번 pop한다.

 

그럼 스택에는 1 2 3 이 남게 된다. 

그다음은 3이므로 pop 한 번 한다.

다음 6이므로 5 6 을 push하고 pop 하여 6을 빼낸다.

 

즉 수열의 각 순서에 따른 수만큼 push하고 top의 수가 현재 순서의 수면 pop하고 아니라면 NO를 출력하고 중단한다.

push는 현재 까지 넣은 수에 따라서 진행한다. 현재까지 넣은 수보다 큰 수가 오면 그 큰 수까지의 수를 push한다.

 

 

 

 

---

🔅 문제 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;


public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        Stack<Integer> stack = new Stack<>();
        int n = Integer.parseInt(br.readLine());

		// 현재까지 넣어진 수
        int currentN = 0;
        for (int i = 1; i < n + 1; i++) {
            int num = Integer.parseInt(br.readLine());

			// 현재까지 넣은 수보다 큰 수면 stack에 push
            if (currentN < num) {
                for (int j = currentN + 1; j <= num; j++) {
                    sb.append("+\n");
                    stack.push(j);
                }
                currentN = num;
            }

			// top의 수가 현재 수열 순서의 수와 같다면 pop
            if (stack.peek() == num) {
                sb.append("-\n");
                stack.pop();
                
            // 아니라면 NO를 출력하고 바로 중지
            } else {         
                bw.write("NO");
                bw.flush();
                bw.close();
                return;
            }

        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();

    }
}

 

---

 

생각보다 쉬운 문제였다.  

 

❗ 오답노트 / 필요한 지식

1. 스택의 기본 원리에 대해 다시 공부하게 되는 계기가 되었다.