[알고리즘] 1874번

._mung·2024년 2월 14일

Algorithm

목록 보기

19/56

오늘 풀어볼 문제는 백준 1874번 문제 "스택 수열" 이다.

이 문제는 실버2 문제이고 스택 문제이다.

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 
스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

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

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. 
push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

이번 문제는 스택에 관한 문제이다. 해당 문제는 7개월 전에 공부삼아 풀어본 문제였다. 그래도 기억이 가물가물하긴 해서 다시 풀어보았다.
풀기 전 스택에 관해 공부를 하자면, 아래와 같다.

Stack
스택은 삽입과 삭제 연산이 후입선출로 이루어지는 자료구조이다. 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다.
쉽게 말하면, 입구가 하나 뿐이 통 안에 순서대로 공을 넣는 것인데 이 통을 상상해보면 처음 넣었던 공이 위에 공들이 쌓이면 빼기 어려운 것처럼 스택도 같다. 먼저 넣은 수는 젤 마지막에 나온다는 특징이 있다. 반대로 말하자면 마지막에 넣은 수가 젤 먼저 나온다.
스택 관련 메서드는 인터넷에 치면 나오니 생략하겠다.

📌첫 번째 도전📌

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer bf = new StringBuffer();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int[] arr = new int[n];

        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Stack<Integer> stack = new Stack<>();
        int num = 1;
        boolean check = true;

        for(int i=0; i < arr.length; i++) {
            int cur = arr[i];
            if(cur >= num) {
                while(cur >= num) {
                    stack.push(num++);
                    bf.append("+\n");
                }
                stack.pop();
                bf.append("-\n");
            }
            else {
                int pop = stack.pop();
                if (pop > cur) {
                    System.out.println("NO");
                    check = false;
                    break;
                }
                else {
                    bf.append("-\n");
                }
            }
        }
        if (check) System.out.println(bf.toString());
    }
}