[Java] baekjoon_1874 : 스택 수열

자료 구조, 스택

스택 수열 : Silver2

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

1874번: 스택 수열

 

 

 

풀이 코드

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

public class Main {
  public static void main(String[] args) throws Exception {
    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

    ArrayList<String> al = new ArrayList<>();
    
    for (int i = 0; i < n; i++) {
      seq[i] = Integer.parseInt(br.readLine());
    }

    Stack<Integer> stack = new Stack<>();
    int num = 1;

    for (int i = 0; i < n; i++) {
      while (stack.isEmpty() || stack.peek() != seq[i]) { // stack이 비어있거나, stack의 top에 있는 값이 수열 i번째의 값과 같지 않을 동안 반복
        stack.push(num); // stack에 num 값 추가
        al.add("+\n");
        num++;

        if (num > n + 1) { // num이 n + 1 보다 클 경우 NO를 반환한 후 종료
          bw.write("NO\n");
          bw.flush();
          bw.close();
          return;
        }
      }

      if (stack.peek() == seq[i]) { // stack의 top에 있는 값이 수열의 i번째의 값과 같다면 
        stack.pop(); // stack의 top에 있는 값 제거
        al.add("-\n");
      }
    }

    for (int i = 0; i < al.size(); i++) {
      bw.write(al.get(i));
    }
    bw.flush();
    bw.close();
  }
}

 

 

Stack

• peek() : Stack의 top에 있는 값을 삭제하지않고 해당 값을 반환
• push(값) : Stack에 값 하나를 스택의 top에 추가
• pop() : Stack 에서 top에 있는 항목을 제거
• isEmpty() : Stack이 비어있을 때 true를 반환한다.

 

---

 

 

문제점 : NO가 출력되는 조건을 어떻게 잡아줘야되는지 생각해 내기 어려웠다.

해결 방법 : 증가시키는 값 num이 n + 1 보다 크게 된다면 수열을 만들 수 없다는 것을 알아냈다.

깨달은 바 : 조건을 잘 생각해서 설정해줘야겠다.