[Baekjoon/Programmers/Programmers] 1874 스택 수열

1874 스택 수열문제 해결 과정.

먼저 지난 번에 내가 구현했던 스택을 이용해서 풀어보았다. 반례 모음의 도움을 받아 8트만에 드디어 성공했고,,, 감사합니다 복받으십셔 처음엔 단순히 수열 내 숫자와 스택의 top에 있는 값과 비교해서 숫자가 top보다 큰 경우에는 해당 숫자가 top이 될 때까지 push하고, 숫자가 top보다 작은 경우는 같아질 때까지 pop을 하며 이 과정에서 top이 -1이 되면 no를 출력하도록 코드를 작성했다. 그러나 여러 반례들이 발견되었다.. 예를 들면 숫자가 top보다 큰 경우 같아질 때까지 top에 push를 하는 과정에서, 이를 제어하지 않아 n까지만 push가 되는 게 아니라 n+1 이상이 push 되었다. isFull라는 boolean 변수를 추가해 n보다 값이 커지는 경우에는 boolean을 true로 만들어 수열 내부에 있는 값까지만 push할 수 있도록 제약을 걸어 주었다. 가족들과 추석 연휴를 보내면서 시도해 본 문제라 다듬을 부분이 매우 많을 것 같다.

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

public class Main {
    public static class Stack {

        int[] stack;
        int top;
        int MAX_ARRAY_SIZE = 100000;

        public Stack() {
            this.stack = new int[MAX_ARRAY_SIZE + 1];
            this.top = 0;
            stack[top] = -1;
        }

        public void push(int x) {
            top++;
            stack[top] = x;
        }
        public int pop() {
            int x = stack[top];
            if (top>0) {top--;};
            return x;
        }
        public int top() {
            return stack[top];
        }
    }

    public static void main(String[] args)  throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Stack stack = new Stack();
        StringBuilder answer = new StringBuilder("");

        boolean isSeries = true;
        boolean isFull = false;

        int n = Integer.parseInt(br.readLine());
        int asc = 1;


        for(int i=1; i<=n; i++) {
            int x = Integer.parseInt(br.readLine());

            if (x>stack.top()) {
                if(asc>x) {
                    isFull = true;
                    isSeries = false;
                }
                while (x > stack.top() && !isFull) {
                    stack.push(asc);
                    answer.append("+").append("\n");
                    asc++;
                }
                if (x == stack.top()) {
                    stack.pop();
                    answer.append("-").append("\n");
                }

            }
            else {
                while(x<=stack.top()) {
                    stack.pop();
                    answer.append("-").append("\n");

                    if (stack.top()==-1 && isFull ) {
                        isSeries = false;
                    }
                }
            }

        }
        System.out.println(isSeries? answer.toString().trim():"NO");
    }
}

같은 코드를 stack을 통해 풀어보았다. 우선 내가 구현한 스택은 논리적으로 스택 내부에 값이 없어도 실제로 -1이라는 값을 갖고 있는 반면, 실제 스택은 값이 없는 경우에 peek() 등의 함수를 호출하면 EmptyStackException이라는 오류가 발생한다. 그래서 다들 굳이 stack을 안쓰고 int 배열을 활용했나보다 empty일 경우의 예외처리를 하나하나 해주는 게 너무 번거로울 것 같아서 stack에 임의의 값 0을 push해주었다. 더 좋은 방법이 떠오르면 고치고 싶다.. 조건문은 이전 코드보다는 훨씬 간결해졌다. 만약 x가 stack의 top값보다 크다면 stack에 값을 더 push하고, 반대의 경우에는 pop하도록 했고, 각각 k와 !empty로 제약 조건을 주었다. 만약 x와 stack의 top값이 같다면 pop하고, 이외의 경우에는 수열을 만들 수 없다는 의미로 isSeries 값을 false로 변경해주었다. 순위권에 랭크된 다른 코드들을 보면 조건문이 훨씬 더 간결하던데 한번 다시 봐야겠다,,,,, 조금 더 문제를 풀어보다보면 더 짧고 간결하게 작성할 수 있지 않을까

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));

        Stack<Integer> stack = new Stack<>();
        StringBuilder answer = new StringBuilder("");

        stack.push(0);

        boolean isSeries = true;

        int n = Integer.parseInt(br.readLine());
        int k = 1;

        for(int i=1; i<=n; i++) {
            int x = Integer.parseInt(br.readLine());

            while(x>stack.peek() && k<=n) {
                stack.push(k);
                answer.append("+").append("\n");
                k++;
            }
            while(x<stack.peek() && !stack.empty()) {
                stack.pop();
                answer.append("-").append("\n");
            }
            if (x== stack.peek()) {
                stack.pop();
                answer.append("-").append("\n");
            } else {
                isSeries = false;
            }
        }
        System.out.println(isSeries? answer.toString().trim():"NO");
    }
}