백준 1874번 : 스택 수열(Java)

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

1874번: 스택 수열

---

[풀이]

 

 먼저, 문제를 이해하는 과정이 어려웠다. 두번, 세번 읽으면서 문제를 이해하려고 노력했는데 내가 이해한 것을 표로 설명해보면 다음과 같다. (첫번째 예제 입력을 예시로 표를 작성했다.)

 

연산 과정	Stack1(연산)	stack_result(결과)	연산자
push 1	{1}	{}	+
push 2	{1,2}	{}	+
push 3	{1,2,3}	{}	+
push 4	{1,2,3,4}	{}	+
pop 4	{1,2,3}	{4}	-
pop 3	{1,2}	{4,3}	-
push 5	{1,2,5}	{4,3}	+
push 6	{1,2,5,6}	{4,3}	+
pop 6	{1,2,5}	{4,3,6}	-
push 7	{1,2,5,7}	{4,3,6}	+
push 8	{1,2,5,7,8}	{4,3,6}	+
pop 8	{1,2,5,7}	{4,3,6,8}	-
pop 7	{1,2,5}	{4,3,6,8,7}	-
pop 5	{1,2}	{4,3,6,8,7,5}	-
pop 2	{1}	{4,3,6,8,7,5,2}	-
pop 1	{}	{4,3,6,8,7,5,2,1}	-

 

-> 표를 보면 알 수 있듯이 stack_result의 결과를 만들 수 있으면 그 과정의 연산자를, 그렇지 않을 경우 NO를 반환하는 것이다. 

 

 이를 위해, 이전의 입력받은 변수를 for문의 index 설정에 사용하였으며 오름차순이 아닐 경우 스택의 최상단 값이 입력받은 값과 같지 않을 경우 NO를 반환 및 종료해야한다.

 

(주의해야할 점)

 

 구현을 하는 것도 그렇지만, 문제를 이해하는 것이 조금 더 어려웠다. 공부하고 있는 입장에서 이렇게 문제가 이해가 안될 경우가 많은데.. 음.. 이 부분도 자연스레 시간이 지나면서 나아질 것이라 생각한다.

 

 이외에는 새로운 임시 변수를 만들어 for문의 인덱스에 사용하는 부분이 또 하나의 주의할 부분이라고 생각한다.

 

---

[코드]

 

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 bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int last_value = 0;

        for (int i = 0; i < n; i++) {
            int value = Integer.parseInt(bf.readLine());

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