[백준/1874] 스택 수열

반응형

[문제]

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

 

첫줄에는 n(1 <= n <= 100,000)이 주어진다. n개의 줄에는 수열을 이루는 1 이상 n이하의 정수가 하나씩 순서대로 주어진다. (중복x)

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력하는데 push연산은 +로, pop연산은 -로 표현하고, 연산이 불가능하면 NO를 출력한다

ex.
입력값 = 8 4 3 6 8 7 5 2 1
결과 =
+ + + + - - + + - + + - - - - -

입력값 = 5 1 2 5 3 4
결과 = 
NO

 

[풀이]

 

import java.util.Stack;
import java.lang.StringBuffer;
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        boolean result = true;
        int n = sc.nextInt(); //배열의 길이 n 받기
        int[] arr = new int[n]; //길이 n인 배열 생성
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt(); // 배열 안의 숫자 받기
        }
        Stack<Integer> st = new Stack<>();
        StringBuffer bf = new StringBuffer();
        int num = 1;
        for(int i=0;i<arr.length;i++){
            if(arr[i]>=num){
                while(arr[i]>=num){
                    st.push(num++);
                    bf.append("+\n");
                }
                st.pop();
                bf.append("-\n");
            }else{
                int stPop = st.pop();
                if(stPop>arr[i]){
                    System.out.println("NO");
                    result = false;
                    break;
                }else{
                    bf.append("-\n");
                }
            }
        }
        if(result){
            System.out.println(bf.toString());
        }
    }
}

 

[출처: 인프런 - Do It 알고리즘 코딩 테스트 강의]