99클럽 코테 스터디 28일차 + [백준] 1874 스택 수열 java 풀이

1. 문제 설명

문제 링크

2. 접근 방식

KEY WORD: DATA STRUCTURE

(0) 현재 조회 중인 수를 value, 출력해야 하는 수를 now라고 해보자.
(1) value <= now 가 성립하지 않을 때까지 value를 stack에 넣고, value++ 한다.
(2) stack의 top과 now를 비교한다.
(3) top이 크면 어떤 방법을 써도 수열을 만들 수 없다. NO를 출력하자.
(왜냐하면, 수열은 무조건 stack에서 pop되는 값으로 만들어야 하기 때문이다. stack에는 오름차순으로 값이 저장되기에, 현 stack의 top 값이 크다고 새로 push를 받으면 더 큰 값밖에 들어오지 않는다. stack의 top이 now보다 작을 때는 같은 값이 들어올 때까지 기다리면 되는 것과 상반된다.)
(4) top == now 이면 stack에서 pop해서 값을 뺀다.

Stack은 진짜 stack 자료구조를 쓰지 않고 배열로 만들어서 풀었다. top이라는 지시자가 바로 현재 stack에서 top의 위치를 나타내는 것이다.

3. 코드 분석

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br   = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb    = new StringBuilder();
        int N               = Integer.parseInt(br.readLine());
        int [] stack        = new int[N+1];
        int top             = 0;
        int value           = 1;

        for (int i = 1; i <= N ; i++) {
            int now = Integer.parseInt(br.readLine());
            while (value <= now) {
                if(value > N) break;
                stack[++top] = value++;
                sb.append("+\n");
            }
            if(stack[top] == now){
                top--;
                sb.append("-\n");
            }
            else if(stack[top] > now){
                System.out.println("NO");
                return;
            }
        }
        System.out.println(sb);
    }
}