boj 1874 수택 수열

 

www.acmicpc.net/problem/1874

1874번: 스택 수열

스택에 1~N을 순서대로 push, pop 과정을 반복하면서 입력에 주어진 순서대로 pop을 할 수 있는지 출력하는 문제입니다.

 

아래의 예시를 이용하여 리뷰하겠습니다.

8
4
3
6
8
7
5
2
1

N = 8, list[] = {4, 3, 6, 8, 7, 5, 2, 1} 입니다.

 

push 1 -> s.peek = 1, list[idx] = 4 (s.peek != list[idx] 이므로 (+))

push 2 -> s.peek = 2, list[idx] = 4 (s.peek != list[idx] 이므로 (+))

push 3 -> s.peek = 3, list[idx] = 4 (s.peek != list[idx] 이므로 (+))

push 4 -> s.peek = 4, list[idx] = 4 (s.peek == list[idx] 이므로 (-)후에 idx++)

              s.peek = 3, list[idx] = 3 (s.peek == list[idx] 이므로 (-)후에 idx++)

              s.peek = 2, list[idx] = 6 (s.peek != list[idx] 이므로 다음 진행)

push 5 -> s.peek = 5, list[idx] = 6 (s.peek != list[idx] 이므로 (+))

push 6 -> s.peek = 6, list[idx] = 6 (s.peek == list[idx] 이므로 (-)후에 idx++)

              s.peek = 5, list[idx] = 8 (s.peek != list[idx] 이므로 다음 진행)

push 7 -> s.peek = 7, list[idx] = 8 (s.peek != list[idx] 이므로 (+))

push 8 -> s.peek = 8, list[idx] = 8 (s.peek == list[idx] 이므로 (-)후에 idx++)

              s.peek = 7, list[idx] = 7 (s.peek == list[idx] 이므로 (-)후에 idx++)

              s.peek = 5, list[idx] = 5 (s.peek == list[idx] 이므로 (-)후에 idx++)

              s.peek = 2, list[idx] = 2 (s.peek == list[idx] 이므로 (-)후에 idx++)

              s.peek = 1, list[idx] = 1 (s.peek == list[idx] 이므로 (-)후에 idx++)

 

여기서 8까지 push 완료하였고, 스택 안의 모든 숫자가 pop되었으므로 순서대로 출력해주시면 됩니다.

만약에 모든 push가 이루어졌는데 pop이 더이상 진행되지 못할 경우에는 NO를 출력해주셔야합니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static Stack<Integer> s = new Stack<>();
    static int list[];
    static int N;
 
    static void func() {
        int idx = 0;
        for (int i = 1; i <= N; i++) {
            s.add(i);
            sb.append("+\n");
            while (!s.isEmpty() && idx < N && s.peek() == list[idx]) {
                s.pop();
                sb.append("-\n");
                idx++;
            }
        }
        
        while(!s.isEmpty() && idx < N && s.peek() == list[idx]) {
            s.pop();
            sb.append("-\n");
            idx++;
        }
        if(!s.isEmpty()) {
            sb = new StringBuffer();
            sb.append("NO\n");
        }
        
        System.out.println(sb.toString());
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = Integer.parseInt(st.nextToken());
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}