알고리즘

백준 1874번 스택 수열 (JAVA)

박카스마시며코딩 2021. 12. 6. 10:51

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

 

1874번: 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

www.acmicpc.net

 

 

입력을 받고 스택의  peek 값이 해당 입력값보다 작으면 해당 숫자까지 스택에 넣어주고, 해당 숫자를 pop합니다.

만약 스택이 비어있거나 peek값이 해당 숫자와 같지 않다면 해당 수열을 만들수 없기 때문에 flag를 false로 만들었습니다.

 

 

package BOJ;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.function.Function;

public class BOJ_1874 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        Deque<Integer> stack = new LinkedList<>();
        int n = stoi.apply(br.readLine());
        int num = 1;
        boolean flag = true;
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i < n ; i++){
            int now = stoi.apply(br.readLine());
            while(stack.isEmpty() || stack.peek() < now){
                stack.push(num++);
                sb.append("+\n");
            }
            if (!stack.isEmpty() && stack.peek() == now){
                stack.pop();
                sb.append("-\n");
            }else{
                flag = false;
            }
//            System.out.println(flag);
        }
        if(!flag){
            System.out.println("NO");
        }else{
            System.out.println(sb.toString());
        }
    }
}