[백준/1874] 스택 수열 (Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/1874
• 분류 : Stack
• 풀이 시간 : 60분

문제 해설

1. 스택 : 후입선출
2. 1~n까지의 수를 오름차순으로 하나씩 스택에 넣으면서 수열을 만듬
3. 임의의 수열이 존재했을 때, push, pop 연산을 통해서 그 수열을 만들 수 있는지 출력

Solution

풀이 접근 방법

1. 스택 = 순서대로 쌓여있음 -> 두번 빼서 가져올 수 없음
   1. 어디다가 뺀 값들을 가지고 있을 수 없음 => 수열 못 만들어짐

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Main{
  static int N;

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

    N = Integer.valueOf(br.readLine());
    // 1 ~ n까지의 수를 넣을 스택
    Stack<Integer> stack = new Stack<Integer>();
    // 숫자를 입력받은 순서
    Queue<Integer> input = new LinkedList<Integer>();
    // 필요한 연산의 순서를 담을 변수
    StringBuilder answer = new StringBuilder();
    // 스택에 담을 1 ~ n 까지의 숫자
    int progressNum = 1;

    // 순열 순서대로 입력받음
    for (int i = 0; i < N; i++) {
      input.add(Integer.valueOf(br.readLine()));
    }

    while (!input.isEmpty()) {
      int value = input.poll();

      // 스택에 들어가야하는 숫자(마지막으로 스택에 들어간 숫자 바로 다음 값) <= 순열의 값
      if (progressNum <= value) {
        // 마지막 숫자부터 ~ 순열의 값까지 스택에 넣고
        while (progressNum <= value) {
          answer.append("+\n");
          stack.add(progressNum++);
        }

        // 스택의 맨 위에 위치한 순열의 값 뽑음
        answer.append("-\n");
        stack.pop();
      } else {
        // 마지막으로 스택에 들어간 숫자 + 1 > 순열의 값
        // 이미 순열의 값은 스택 안에 들어가있다는 의미
        // 스택 맨 위의 값이랑 순열의 값이랑 같은지 비교
        if (stack.peek() == value) {
          answer.append("-\n");
          stack.pop();
        } else {
          // 무조건 같아 다음 단계 진행 가능!!
          // 두번 빼면 가져올 수 없음
          answer = new StringBuilder("NO");
          break;
        }
      }
    }

    bw.write(answer.toString() + "\n");
    bw.flush();
    bw.close();
  }

}