[백준] 1874번. 스택 수열(JAVA)

문제

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

---

풀이(n일)

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

public class Main{

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

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

        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int max = 0;
        try{
            for(int i = 0; i < n; i++){
                int target = arr[i];
                while (max < target){
                    max += 1;
                    stack.push(max);
                    sb.append("+\n");
                }
                int pop = stack.pop();
                sb.append("-\n");
                while(pop != target){
                    pop = stack.pop();
                    sb.append("-\n");
                }
            }
        }catch (EmptyStackException e){
            System.out.println("NO");
            return;
        }

        System.out.println(sb);
    }
}

 

문제 자체를 이해하는데 오랜 시간이 걸려 n일이 걸린 문제이다. 실버2라는 난이도를 갖고 있기에 문제를 직접 이해하고 풀고 싶어 생각날 때마다 문제를 들여다보며 해결해보려고 했다.

 

문제에 대한 이해는 다음과 같다. 오름차순으로 집어넣는다!!(이 부분이 오래걸렸다.) 이 후 하나씩 뽑아 문제에서 제시한 수열을 만들 수 있냐를 보는 것이다.

 

예를 들어보자. 나에겐 처음에 빈 스택이 존재하고, 내가 원하는 수열은 5 4 3 2 1이다.

그럼 어떻게 하면 스택에 오름차순으로 집어넣으며 원하는 수열을 출력할 수 있을까?

1. 바로 처음에 5개를 연속으로 넣으면 된다.(1,2,3,4,5) 순으로 스택에 집어넣게 된다.

2. 이후 하나씩 꺼내서 나열하면 된다는 것이다.

연산으로 따지면 + + + + + - - - - -를 하면 된다는 것이다.

 

이후 문제 해결에는 어려운 부분은 없었으나 굳이 스택에 대한 비교를 어렵게 만들고 싶지않아 에러가 뜨는 경우 NO를 출력하고 끝내는 것으로 작성했다.