[백준 - 1874] 스택 수열 - Java

문제 설명

 

1874번: 스택 수열

 

접근 방법

해당 문제는 이름에 맞게 스택 자료구조를 이용하여 해결할 수 있었습니다.

 

문제에서 주어진 예시로 스택 자료구조를 직접 그려보면서 접근해보니 수월하게 해결할 수 있었습니다. 우선 최초 스택 자료구조가 비어있다고 가정했을 때, 최초 4라는 숫자를 만난다면 1 ~ 4의 숫자를 스택에 push 하고 마지막 숫자 4를 pop 시켜야 합니다. 이때 스택 자료구조는 다음과 같은 형태가 됩니다.

 

이후에 3이라는 숫자를 만난다면 현재 스택의 최상위 요소가 3이므로 그대로 pop 하면 됩니다.

 

 

이후에 6이라는 숫자를 만나면 5 ~ 6의 숫자를 push하고 마지막 숫자 6을 pop 합니다. (앞서 4까지 push 했으닌까 다음 push 대상 숫자는 5입니다.)

 

 

여기까지만 그려보아도 문제 해결에 대한 아이디어를 얻을 수 있었습니다. 우선 마지막으로 push된 숫자(max)가 입력되는 값(number)보다 작다면(max < number) 마지막으로 push된 숫자에 + 1을 한 숫자(max + 1)부터 입력되는 값(number) 까지의 숫자를 push 해주고 마지막 숫자(number)를 pop하면 됩니다. 이제 마지막으로 push된 숫자는 number가 되게 됩니다.

 

            number = Integer.parseInt(br.readLine());

            if (max < number) {
                for (int j = max + 1; j <= number; j++) {
                    stack.push(j);
                    result.add('+');
                }
                stack.pop();
                result.add('-');
                max = number;
            }

 

반대로 마지막으로 push된 숫자(max)가 입력되는 값(number) 보다 크다면 현재 스택 자료구조상 최상위에 있는 요소의 값이 입력되는 값(number)과 동일해야만 문제에서 요구하는 스택 수열 조건을 충족시킬 수 있습니다. 동일하다면 그대로 pop시키면 되고 동일하지 않다면 조건을 충족시킬 수 없으므로 "NO"를 출력하도록 합니다.

 

            else if (max > number) {
                if (stack.peek() == number) {
                    stack.pop();
                    result.add('-');
                } else {
                    System.out.println("NO");
                    return;
                }
            }

 

참고로 문제에서 동일한 숫자는 주어지지 않기 때문에 마지막으로 push된 숫자와 입력되는 값(number)는 동일할 수가 없으므로 별도로 고려할 필요가 없습니다.

 

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class Main {

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

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

        Stack<Integer> stack = new Stack<>();
        List<Character> result = new ArrayList<>();
        int number, max = 0;

        for (int i = 0; i < n; i++) {

            number = Integer.parseInt(br.readLine());

            if (max < number) {
                for (int j = max + 1; j <= number; j++) {
                    stack.push(j);
                    result.add('+');
                }
                stack.pop();
                result.add('-');
                max = number;
            } else if (max > number) {
                if (stack.peek() == number) {
                    stack.pop();
                    result.add('-');
                } else {
                    System.out.println("NO");
                    return;
                }
            }
        }

        for (Character character : result) {
            System.out.println(character);
        }
    }
}

 

참고 자료

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