[Java11] 백준 1874번 : 스택 수열

백준 1874번 : 스택 수열

1~n까지 순서대로만 push 할 수있는 스택을 사용하여 수열을 만들때 어떤 순서로 push, pop해야 해당 수열을 만들수 있는지를 구하는 문제이다.

입력으로 들어온 숫자는 head의 data보다 큰 경우와 작은경우 2가지 경우로 나눌 수 있다.
만약 더 큰 숫자라면 같아질때 까지 push를 한 후 pop으로 출력해야하고, 아니라면 pop을 통해 출력하면 된다. pop으로 출력하는 동작이 중복되니 if-else문이 아닌 while의 조건으로 분리했다. 그리고 pop을 했을때의 결과가 입력과 같으면 계속해서 진행하면 되고 다르다면 즉시 종료하고 NO를 출력한다.

처음에 제출했을때 틀렸습니다 판정을 받았는데, 조건이 틀렸을때 바로 종료하지 않고 다음 숫자를 계속 입력받도록 만들었더니 발생한 문제였다.

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

public class Baekjoon_1874 {
  static class Stack {
    static class Node {
      private final int data;
      private Node next;

      public Node(int data) {
        this.data = data;
        this.next = null;
      }
    }

    private Node head;


    public void push(int data) {
      Node newNode = new Node(data);
      newNode.next = head;
      head = newNode;
    }

    public int pop() {
      if (head == null) return -1;
      int result = head.data;
      head = head.next;
      return result;
    }
  }

  public void result() throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력받기
    StringBuilder sb = new StringBuilder();

    Stack stack = new Stack();
    int now = 1;

    String str = br.readLine(); // 한줄씩 받기
    StringTokenizer st = new StringTokenizer(str); // " "를 기준으로 나눈기
    int n = Integer.parseInt(st.nextToken());

    for (var i = 0; i < n; i++) {
      str = br.readLine(); // 한줄씩 받기
      st = new StringTokenizer(str); // " "를 기준으로 나눈기
      int input = Integer.parseInt(st.nextToken());

      while (now <= input) { // push 할만큼 하기
        stack.push(now++);
        sb.append("+").append('\n');
      }
      if(stack.pop() == input){ // 출력해야하므로 pop하고 값 비교하기
        sb.append("-").append('\n');
      } else {
        sb.setLength(0);
        sb.append("NO").append('\n');
        break; // 조건에 벗어나면 바로 break 해줘야한다.
      }
    }
    System.out.println(sb);
    br.close();
  }

  public static void main(String[] args) throws Exception {
    new Baekjoon_1874().result();
  }
}