1874번 스택 수열(java)

 

이 문제를 처음 접하면 저처럼 예제 출력이 왜 이렇게 출력되는지 몰라 조금 해맬 수 있다고 생각해 한 번 살펴보도록 하겠습니다.

 

예제 이해

 

 해당 문제에서 가장 중요한 문구는 '임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 연산을 수행해야 하는지' 라고 생각합니다.

 

 예제 입력 1을 보면 8개의 숫자를 입력받고 4를 만드려면 push(1), push(2) , push(3) , push(4) 하고 pop()을 수행해야 합니다. 생각을 조금 더 해보자면 아래와 같이 예제가 출력된다는 것을 알 수 있습니다.

 

+	1
+	2
+	3
+	4
-		4
-		3
+	5
+	6
-		6
+	7
+	8
-		8
-		7
-		5
-		2
-		1

 

-인 pop()을 한 숫자를 나열해보면 예제 출력 1 처럼 출력된다는 것을 알 수 있습니다.(4 3 6 8 7 5 2 1)

 

 예제 입력 2를 아래와 같이 보면 수열이 만들어지지 않는 경우를 알 수 있습니다.

 

+	1
-		1
+	2
-		2
+	3
+	4
+	5
-		5
-		4
-		3 -> 찾기 위해 4를 pop() 해버림... 그 결과는 4를 찾지 못해 아래와 같습니다.
NO

 

구현 코드

 

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

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        int j = 1;
        boolean flag = true;

        for (int i = 0; i < n; i++){
            int k = Integer.parseInt(br.readLine());
            if (j <= k){
                for (; j <= k; j++){
                    stack.push(j);
                    sb.append("+\n");
                }
            }else {
                if (stack.peek() != k){
                    flag = false;
                }
            }
            stack.pop();
            sb.append("-\n");
        }

        if (flag){
            System.out.print(sb);
        }else {
            System.out.print("NO");
        }

        br.close();
    }
}

 

코드 설명

 

 Stack을 만들고 전역 변수로 선언된 j 값과 현재 입력된 수(k)의 대소 관계 중 j가 k와 작거나 같을 경우 증가하는 j의 값을 Stack에 push()를 하고 StringBuulder에 +를 append() 해줍니다. 이후 수열을 만들기 위해 맨 위의 값을 pop() 해주고 마찬가지로 -를 append() 해줍니다.

 

 j가 k와 작거나 같을 경우 이외에는 Stack의 맨 위 값을 peek() 하여 k의 값과 다르다면 NO를 출력하도록 코드를 구현했습니다.