[Baekjoon/JAVA] 1874번 - 스택 수열

Baekjoon Online Judge

문제로 이동

 

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

 

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

 

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

 

---

예제 입력	예제 출력
8 4 3 6 8 7 5 2 1	+ + + + - - + + - + + - - - - -
5 1 2 5 3 4	NO

---

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Stack stack = new Stack();

        int n = in.nextInt();
        int j = 1;
        boolean isNo = false; // 불가능 여부

        for (int i = 0; i < n; i++) {
            int num = in.nextInt();

            // num이 스택에 포함될 때까지 push
            if (stack.peek() < num) {
                int m = 0;
                for (; j <= num; j++) {
                    stack.push(j);
                    m++;
                }

                stack.pop();
                stack.arrSet(i, true, m + 1);
            }
            // 가장 위에 있는 숫자기 num과 같을 때
            else if (stack.peek() == num) {
                stack.pop();
                stack.arrSet(i, false, 1);
            }
            else {
                isNo = true;
                break;
            }
        }

        // 출력
        if(isNo)
            System.out.println("NO");
        else {
            for (int i = 0; i < n; i++)
                stack.print(i);
        }
    }
}

class Stack {
    private int top = -1;
    private int[] data = new int[100001]; // 데이터
    public int[] count = new int[100001]; // +나 -가 나오는 횟수
    public boolean[] isPlus = new boolean[100001]; // +, - 여부

    // 삽입 함수
    public void push(int n) {
        data[++top] = n;
    }

    // 삭제 함수
    public int pop() {
        if (isEmpty())
            return 0;
        else
            return data[top--];
    }

    // 스택이 비어있는지 확인
    public boolean isEmpty() {
        return top == -1;
    }

    // 맨 위의 데이터 가져오기
    public int peek() {
        if (isEmpty())
            return 0;
        else
            return data[top];
    }

    // 배열에 값 입력
    public void arrSet(int i, boolean b, int n) {
        isPlus[i] = b;
        count[i] = n;
    }

    // 출력
    public void print(int num) {
        for (int i = 0; i < count[num]; i++) {
            if (isPlus[num] && i != count[num] - 1)
                System.out.println("+");
            else
                System.out.println("-");
        }
    }
}

일단 클래스로 스택을 구현한 뒤 문제를 풀었다.

 

        int n = in.nextInt();
        int j = 1; // 스택에 숫자를 어디까지 넣었는가
        boolean isNo = false; // 불가능 여부

        for (int i = 0; i < n; i++) {
            int num = in.nextInt();

            // num이 스택에 포함될 때까지 push
            if (stack.peek() < num) {
                int m = 0; // push를 호출한 횟수
                for (; j <= num; j++) {
                    stack.push(j);
                    m++;
                }

                stack.pop();
                stack.arrSet(i, true, m + 1);
            }
            // 가장 위에 있는 숫자기 num과 같을 때
            else if (stack.peek() == num) {
                stack.pop();
                stack.arrSet(i, false, 1);
            }
            else {
                isNo = true;
                break;
            }
        }

main에서 클래스로 구현한 스택을 이용해 문제를 푸는 부분이다. 일단 숫자를 num에 입력 받는다.

- 그 수가 스택의 가장 위에 있는 수보다 크다면 아직 스택에 해당 숫자가 포함되어 있지 않는 것이기에 push()로 스택에 num까지의 숫자를 입력했다. 여기서 입력되는 숫자의 시작은 j에 저장되어 있는 수로, 중복되어서 숫자가 입력되는 것을 방지하기 위함이다.  이 반복이 끝나면 num을 스택에서 빼기 위해 pop()을 한 번 호출한다. 그리고 arrSet()에 i, push()를 호출했으니 true와 m + 1(마지막에 pop()을 호출했기에)를 넣어서 호출한다. arrSet()에 대한 설명은 아래에 서술한다.

- num이 스택의 가장 위에 있는 수와 같다면 pop()을 한번 호출한다.

- 그 외의 경우는 해당 수열을 만드는 것은 불가능한 것이기에 isNo에 true를 입력하고 반복을 종료시킨다.

 

    // 배열에 값 입력
    public void arrSet(int i, boolean b, int n) {
        isPlus[i] = b;
        count[i] = n;
    }

    // 출력
    public void print(int num) {
        for (int i = 0; i < count[num]; i++) {
            if (isPlus[num] && i != count[num] - 1)
                System.out.println("+");
            else
                System.out.println("-");
        }
    }

isPlus[]는 해당 인덱스의 수열을 만드는데 push(+)나 pop(-) 중 어느 것을 사용했는지를 저장하는 배열이다. count[]는 이 push()나 pop()이 몇 번 호출되었는지를 저장하는 배열이다.

arrSet()은 위의 정보를 배열에 정하는 함수이며, print는 위의 배열에 맞게 +와 -를 출력하는 함수이다. 

 

        // 출력
        if(isNo)
            System.out.println("NO");
        else {
            for (int i = 0; i < n; i++)
                stack.print(i);
        }

main에서 결과에 따른 출력을 하는 부분이다. 만약 isNo가 true라면 이 수열은 불가능한 것이기에 "NO"를 출력하고 그렇지 않다면 print()를 호출해서 답을 출력한다.