Boj-1874번/java/스택과 큐

 

 생각보다 많이 어렵고 시간을 오래 쓴 문제.

 

 문제를 풀 때는 답이 보이지 않고 너무 어려웠으나 
 결국 메모장에서 스택의 모습을 대충 작성해보며 관찰하니
그동안 내가 잘못 생각해왔던 부분들을 바로 알 수 있었고 금방 고칠 수 있었다.

 

 이런 자료형이나 스택을 쓸 때는 주석이건 메모장이건 활용해서 적극적으로 예시, 가시화를 활용하자.

머릿속으로만 생각하니 더 까다로워지는 것은 당연하다.

 

 구체적 한 부분의 스냅샷을 찍어서 그 알고리즘을 직접 관찰하는 느낌으로 진행하는 습관을 기르면 좀 더 금방 풀 수 있을 것 같음.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        boolean result = true;

        int n = Integer.parseInt(br.readLine());
        //n번 반복
        int[] array = new int[n];
        Stack<Integer> stack = new Stack<>();
        int num =1;
        for(int i=0;i<n;i++){
            array[i] = Integer.parseInt(br.readLine());
        }
        //n개의 입력받은 수들에 대해 걔네를  +와 -로 표현해야한다.
        for(int i=0;i<n;i++){
            // k = 목표 수
            int k = array[i];
            //일단 스택에다 num을 목표수와 똑같아질때까지 넣는다.
            if(k>=num){
                while(k>=num) {
                    stack.push(num);
                    num++;
                    sb.append("+\n");
                }
                stack.pop();
                sb.append("-\n");
            }

            //스택에 들어간 num이 더 작은 경우(스택 안에 해당 수 존재)
            else{
                int last = stack.pop();
                if(last>k){
                    result=false;
                    System.out.println("NO");
                    break;
                }
                else{
                    sb.append("-\n");
                }
            }

         

        }
        if(result) {
            System.out.println(sb);
        }

    }

}