99클럽 코테 스터디 28일차 TIL / [백준] 스택 수열

오늘의 학습 키워드

---

Stack

문제

---

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

• 플랫폼: 백준
• 문제명: 스택 수열
• 난이도: 실버 2

풀이

---

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        Queue<Integer> answerQueue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            answerQueue.offer(Integer.parseInt(br.readLine()));
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            while (!stack.isEmpty() && stack.peek().equals(answerQueue.peek())) {
                stack.pop();
                answerQueue.poll();
                sb.append('-').append("\n");
            }

            if (!stack.isEmpty() && stack.peek() > answerQueue.peek()) {
                System.out.println("NO");
                return ;
            }

            stack.push(i);
            sb.append('+').append("\n");
        }

        while (!stack.isEmpty()) {
            if (!stack.pop().equals(answerQueue.poll())) {
                System.out.println("NO");
                return;
            } else {
                sb.append('-').append("\n");
            }
        }

        System.out.println(sb);
    }
}

접근

• 1부터 n까지의 값을 순서대로 stack에 넣을 때, 입력 값으로 주어지는 수열을 만들 수 있는지 확인하는 문제입니다.
• 그대로 1부터 n까지의 값을 순서대로 넣을 stack과, 입력 값으로 주어지는 수열을 담을 answerQueue를 만들었습니다.
• 이후 스택에 값을 삽입하며 answerQueue의 peek 값과 stack의 peek 값이 같은 경우 pop을 해줬습니다.
  • 이 과정에서 만약 stack의 peek 값이 answerQueue의 peek 값보다 큰 경우에는 수열을 만들 수 있는 방법이 존재하지 않기에 곧바로 종료하도록 처리 했습니다.
    • 존재할 수 없는 이유
      • 로직상 answerQueue의 peek 값이 나올때까지 stack에 값을 삽입하므로, 바로바로 그 값들이 처리되기 마련입니다.
      • 만약 answerQueue의 peek 값이 더 작아버린다면 stack에 담긴 값들을 pop하며 찾아야 하는데, 이렇게 되면 길이가 n짜리인 수열을 만들 수 없게 됩니다.

소요 시간

30분