[백준/자바] 1874 : 스택 수열

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

1874번: 스택 수열

---

스택을 활용한 문제이다.

push하는 순서가 오름차순이므로 1부터 n까지 차례대로 push 한다고 생각하면 된다.

 

내가 생각한 풀이 방안은 다음과 같다.

 

• 현재까지 넣은 수가 현재 차례의 배열값보다 작거나 같다면 push -> 크다면 바로 top과 비교
• push 작업이 끝난 후 스택의 top 값이 현재 배열값과 같다면 pop
• 같지 않다면 스택을 통해 만들 수 없는 수열이므로 NO 출력

제일 헤맨 부분은 while 조건문이다.

첫 번째로 생각한 방식은 다음과 같다.

  1. 스택 끝까지 연산 순서를 확인하려면 스택이 빌 때까지 연산을 해야 했고, 

  2. push하는 숫자가 n보다 작거나 같아야 한다.

while(!stk.empty() || num <= N) { ... }

하지만 수열이 담긴 배열을 다 돌기만하면 되는 거여서 다음과 같이 수정하였다.

while(idx < N) { ... }

 

최종 풀이는 다음과 같다.

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

public class Boj_1874 {

   public static void main(String[] args) throws NumberFormatException, IOException {
       // TODO Auto-generated method stub
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringBuilder sb = new StringBuilder();

       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> stk = new Stack<Integer>();
       int num = 1; // 스택에 넣는 숫자
       int idx = 0; // 배열 인덱스

       while(idx < N) {
           if(num <= arr[idx]) {
               for(int i = num-1; i<arr[idx]; i++) {
                   stk.push(num++);
                   sb.append("+\n");
               }
           }

           if(stk.peek() == arr[idx++]) {
               stk.pop();
               sb.append("-\n");
           }else {
               System.out.println("NO");
               return;
           }
       }

       System.out.println(sb);
   }
}