[JAVA] 백준 1874번: 스택 수열 (기초 1-4)

문제

스택 (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

 

8개의 문자열이 들어온다.

첫번째 문자열 4

스택에 1, 2, 3, 4를 넣는다. (+, +, +, + 를 출력)

스택에서 4를 뺀다. (- 를 출력)

스택에 남아 있는 수 (1, 2, 3)

 

두번째 문자열 3

스택에서 3을 뺀다. (-를 출력)

스택에 남아 있는 수 (1, 2)

 

세번째 문자열 6

스택에 4까지 넣었기 때문에 4 이후의 수인 5, 6을 집어 넣는다. (+, +를 출력)

스택에서 6을 뺀다. (-를 출력)

스택에 남아 있는 수 (1, 2, 5)

 

네번째 문자열 8

스택에 7, 8을 넣는다. (+, +를 출력)

스택에서 8를 뺀다. (-를 출력)

스택에 남아 있는 수 (1, 2, 5, 7)

 

다섯번째 문자열 7

스택에서 7을 뺀다. (-를 출력)

스택에 남아 있는 수 (1, 2, 5)

 

여섯번째 문자열 5

스택에서 5를 뺀다. (-를 출력)

스택에 남아 있는 수 (1, 2)

 

일곱번째 문자열 2

스택에서 2를 뺸다. (-를 출력)

스택에 남아 있는 수 (1)

 

여덟번째 문자열 1

스택에서 1을 뺀다. (-를 출력)

 

 

문제 이해가 되었는가?

이제 문제를 풀어보자

 

1. stack에 0을 집어 넣는다. (초기화)

ArrayList<String> resultList = new ArrayList<>();
stack.push(0);

 

2. 입력 문자열의 숫자가 stack의 들어있는 마지막 숫자보다 클 때

stack의 마지막 숫자 +1 부터 입력 문자열의 수까지 stack에 넣는다.

visit 어레이를 이용하여 stack에 들어온 적이 없는 숫자만 stack에 집어 넣는다.

stack에 숫자를 넣을 때 마다 결과로 출력할 문자열인 +도 따로 저장을 해준다.

모든 숫자를 다 넣었다면 마지막 수를 pop으로 뱉어낸다.

결과에 출력할 -도 따로 저장해준다.

if (temp > stack.peek()) {
    for (int j = stack.peek() + 1; j <= temp; j++) {
        if (!visit[j]) {
            visit[j] = true;
            stack.push(j);
            resultList.add("+");
        }
    }
    stack.pop();
    resultList.add("-");
}

 

3. 입력 문자열의 숫자가 stack에 마지막 숫자와 같을 때

pop으로 마지막 수를 빼낸다.

결과에 출력할 - 문자열도 따로 저장한다.

else if (temp == stack.peek()) {
  stack.pop();
  resultList.add("-");
}

 

4. 입력 문자열의 숫자가 stack에 마지막 숫자보다 작을 때

"NO" 를 출력하고 프로그램을 종료한다.

else if (temp < stack.peek()) {
  System.out.println("NO");
  System.exit(0);
}

 

5. 모든 문자열을 입력 받았다면 결과로 출력하기 위한 어레이 (resultList)에 있는 문자열을 순서대로 출력해준다.

for (String s : resultList) {
    System.out.println(s);
}

 

전체 코드는 아래와 같다.

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class baekjoon1874 {
    public static void main(String[] args) {
        // 새로운 숫자가 현재 숫자보다 클 때
        // push를 이용해서 새로운 숫자 까지 넣고, 현재 숫자 = 새로운 숫자
        // 새로운 숫자 pop 하고, 현재 숫자--;

        // 새로운 숫자가 현재 숫자와 동일할 때
        // 현재 숫자 pop, 현재 숫자--;

        // 새로운 숫자가 현재 숫자보다 작을 때
        // pop을 해서 새로운 숫자가 나오면, 현재 숫자--;
        // pop을 해서 새로운 숫자가 안나오면 "NO" 출력 시스템 종료
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        Stack<Integer> stack = new Stack<>();
        ArrayList<String> resultList = new ArrayList<>();
        stack.push(0);
        boolean[] visit = new boolean[n + 1];
        for (int i = 0; i < n; i++) {
            int temp = sc.nextInt();
            if (temp > stack.peek()) {
                for (int j = stack.peek() + 1; j <= temp; j++) {
                    if (!visit[j]) {
                        visit[j] = true;
                        stack.push(j);
                        resultList.add("+");
                    }
                }
                stack.pop();
                resultList.add("-");
            } else if (temp == stack.peek()) {
                stack.pop();
                resultList.add("-");

            } else if (temp < stack.peek()) {
                System.out.println("NO");
                System.exit(0);
            }
        }
        for (String s : resultList) {
            System.out.println(s);
        }
    }
}