[BOJ] 1874.스택 수열(Stack)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

stack에 열심히 push 해주다가

입력된 수열과 stack의 peek가 같다면 pop해주면 된다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;   public class BOJ1874 {          static int N;     static int[] nums;          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringBuilder sb = new StringBuilder();                  N = Integer.parseInt(br.readLine());         nums = new int[N];         for (int i = 0; i < N; i++)              nums[i] = Integer.parseInt(br.readLine());                   int[] stack = new int[N];         int top = -1;         int idx = 0;         for (int i = 1; i <= N; i++) {             // 일단 push             stack[++top] = i;             sb.append("+" + "\n");             // 입력된 수열의 idx번째 수와 stack의 peek가 같다면 pop             while(nums[idx] == stack[top]) {                 sb.append("-" + "\n");                 top--;                 idx++;                 if(top < 0 || idx > N) break;             }         }         if(top == -1 && idx == N)                  System.out.println(sb);         else {             sb.substring(0, sb.length());             System.out.println("NO");         }                      br.close();     }      } Colored by Color Scripter

cs

line 25~26) 일단 열심히 push

line 28~33) 입력된 수열의 idx번재 수와 stack의 peek가 같다면 계속 pop을 해주면 된다.

line 35) 만일 top이 -1이고, idx가 N과 같다면 모든 수열이 다 출력된 것이므로 그동안 쌓아둔 연산을 출력

line 37~40) 그렇지 않다면 NO 출력