[알고리즘 PS] 백준 1874 스택 수열 Java 문제 풀이

문제

해당 포스팅은 백준의 1874번 스택 수열 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

문제

예제 입력 & 출력

 

해결법

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지와 어떤 트릭을 피애햐 할지를 생각해보는 오답 후보를 나눠 생각해보자.

이 문제는 특이하게, 문제에서 스택을 사용하라고 권장하듯 말한다.

문제에서 제시한 그대로 스택을 사용해서 접근하면 쉬운 풀이를 할 수 있다.

 

이 문제는 스택 또는 배열을 이용해서 풀 수 있는데, 다른 사이트를 참고해보니 배열을 이용한 풀이가 압도적으로 많아서 필자는 스택을 이용해서 풀어보도록 하겠다.

접근법

스택 수열 문제에서 가장 어려운 부분은 바로 문제를 제대로 파악하는 것이다.

• 만약 n이라는 수를 만나게 된다면, 1~n 까지 스택에 push 한다.
• stack의 top이 n과 같아진다면 스택에서 pop 한다.
• n을 stack에 push 하는 과정에서 한 번 나간 혹은 들어온 수는 중복되면 안된다.

자세한 설명은 이곳에서 확인할 수 있다.

오답 후보

오답 후보는 1가지로 모든 케이스를 커버할 수 있다.

1. 입력 값이 마지막으로 들어온 값 보다 작을 경우, 스택의 최상단의 값과 현재 입력 값이 다를 때.

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();

        int n = Integer.parseInt(br.readLine());
        int cursor = 0; // 마지막 최종 위치

        while(n-- > 0) {
            int input = Integer.parseInt(br.readLine());

            if(input > cursor) {
                for(int i = cursor+1; i <= input; i++ ){
                    stack.push(i);
                    sb.append("+\n");
                }
                cursor = input;
            }else if (stack.peek() != input) {
                System.out.println("NO");
                return;
            }
            stack.pop();
            sb.append("-\n");
        }
        System.out.println(sb.toString());
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.