백준 1874번 - 스택 수열

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

1874번: 스택 수열

 

---

 

문제 분석

제목과 같이 스택을 이용한 문제다.

개인적으로 처음에 문제 이해가 좀 안됐는데

입력값 n 이 주어지면 스택에 들어올 수 있는 1~n 까지의 숫자가 오름차순 순서대로 주어지게 되고,

이 1~n 까지 숫자를 순서대로 스택에 쌓을 수 있다.

그리고 n값 이후 입력으로 들어오는 수열이 그 스택이 pop 될때마다 반환되는 숫자의 나열이라고 보면 된다.

 

위와 같은 방법으로 push, pop 연산을 통해 입력받은 수열을 만들 수 있을 경우엔 push연산이 일어날 때 +, pop 연산이 일어날 때 - 를 출력하면 되고,

만약 수열을 만들 수 없을 경우엔 NO를 출력한다.

 

---

풀이

입력받은 수열(int 배열)을 순회하며

수열의 각각의 값마다 스택 가장 위의 값과 비교(스택의 가장 위에 있는 값을 읽을 수 있는 peek() 사용)하여

peek 값이 적을 경우 해당 값만큼 push, 같을 경우 pop, 적을 경우엔 바로 NO를 반환하도록 하였다.

 

1. 스택 생성.

   peek() 메서드는 스택에 값이 없을 경우 EmptyStackException 이 발생하기 때문에

   미리 수열과는 상관없는 0을 넣어주었다.

2. 1 ~ n 의 값이 담긴 배열 numbers 생성,

    numbers 내의 숫자들이 어디까지 사용되었는지 표시하기 위한 idx 변수도 생성

3. 입력 수열 arr를 순회한다.
    (현재 값 : c, 현재 스택의 peek()한 값: peek 으로 표기)
   3-a. peek 이 c 보다 작을 경우

           현재 스택에 숫자를 c만큼 채워줘야 한다.
           while 문을 통해 idx(현재 numbers의 인덱스를 가리키고 있는 변수) < c 까지 반복하여

           스택에 push() 해준다. 이때, StringBuffer에 "+" 를 append 해준다.

   3-b. peek과 c 가 같을 경우

           수열에 해당하는 값이기 때문에 스택 pop() 해준다. 이때, StringBuffer에 "-" 를 append 해준다.

   3-c. peek이 c 보다 클 경우

           c가 peek값 이전에 들어간 값이기 때문에 c를 꺼내려면 pop()을 먼저 해야되므로 수열 순서가 맞지 않게 된다.
           바로 "NO" 를 출력하고 종료하도록 한다.

4. StringBuffer에 저장된 값을 toString()을 통해 출력

---

코드

public class Example1874 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        solution(n, arr);
    }

    public static void solution(int n, int[] arr) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int[] numbers = new int[n];
        int idx = 0;
        for (int i = 1; i <= numbers.length; i++) {
            numbers[i-1] = i;
        }

        StringBuffer sb = new StringBuffer();

        for (int c : arr) {
            if (stack.peek() < c) {
                while (idx < c) {
                    stack.push(numbers[idx++]);
                    sb.append("+\n");
                }
            }
            if (stack.peek() == c) {
                stack.pop();
                sb.append("-\n");
            }
            if (stack.peek() > c) {
                System.out.println("NO");
                return;
            }
        }

        System.out.println(sb.toString());
    }
}

---

댓글 피드백은 언제나 환영합니다!