[BOJ][Java]1874번 스택 수열

 

문제

 

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

 

문제의 이름부터 대놓고 스택 수열 이기 때문에 스택을 이용해서 해결하면 된다.

자연수 1부터 N까지 순차적으로 stack에 push 해야 한다는 조건이 있으므로

이 부분만 유의하면 된다.

 

로직을 간단히 생각해보면 

자연수를 num = 1; 로 선언하고,

주어진 수열을 4,3,6,8,7,5,2,1 이라고 했을때

수열을 하나씩 순회하면서 현재 값을 now 라고 한다면

 

1. stack 이 비어있을땐 num넣고, num++;

2. stack의 마지막 값이 now 보다 작다면 num넣고, num++;

3. stack의 마지막 값이 now와 같다면 pop();

4. stack의 마지막 값이 now보다 작다면 -> 이 경우에는 스택연산으로 해당 수열을 만들 수 없으므로 "NO" 출력

 

과 같은 로직으로 짤 수 있다.

마지막으로 문자열을 출력할때는 System.out.println() 이 아닌

StringBuilder() 를 사용하는것이 성능상 매우 유리하다.

package boj;

import java.util.*;
import java.io.*;

public class BOJ1874 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Stack<Integer> stack = new Stack<>();

        int N = Integer.parseInt(st.nextToken());

        StringBuilder sb = new StringBuilder();

        int num = 1;
        boolean flag = true;

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            int now = Integer.parseInt(st.nextToken());

            while(true){
                if(stack.isEmpty()){
                    stack.push(num);
                    num++;
                    sb.append("+");
                    sb.append("\n");
                }else if(stack.peek() < now){
                    stack.push(num);
                    num++;
                    sb.append("+");
                    sb.append("\n");
                }else if(stack.peek() == now){
                    stack.pop();
                    sb.append("-");
                    sb.append("\n");
                    break;
                }else{
                    flag = false;
                    break;
                }
            }

            if(!flag) break;

        }

        if(flag) System.out.println(sb.toString());
        else{
            System.out.println("NO");
        }

    }
}