[JAVA]백준 1874번: 스택 수열

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

1874번: 스택 수열

1. 문제 설명

 

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로, 하나의 수열을 만들 수 있다.

스택에 push 하는 순서는 반드시 오름차순이다.

임의의 수열이 주어졌을 때, 스택을 이용하여 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push pop 연산을 수행해야 하는지 출력하는 문제이다.

(push -> +, pop -> - 출력, 안될 시 NO 출력)

 

2. 풀이

 

Stack에 대한 이해가 있다면 구현은 간단하다.

 

오름차순으로 스택에 숫자를 넣을 수 있기 때문에 발생할 수 있는 상황은 3가지가 있다.

 

1. 현재 입력받은 숫자 (임의의 수열 중 한 수)가 stack의 top보다 값이 큰 경우

- 이 경우에는 max+1 값에서부터 현재 입력받은 숫자까지 stack에 넣고 현재 입력받은 숫자를 pop 하여 임의의 수열을 만들 수 있다.

- max 값이 필요한 이유는 1번 경우에서 push를 할 때 현재 stack의 top보다 큰 수부터 push 하는 것이 아니라 기존에 pop 했던 값부터 시작하여 push를 해야 하기 때문이다.

- 예를 들면 스택에 1,2,3 이 있고 3을 pop한 경우 스택의 top은 2를 가리킨다. 그다음 push를 할 때는 top보다 큰 수 3부터 다시 push 하는 것이 아니라 max 값 3보다 큰 4부터 push를 해야 한다.

- 연산을 수행 한후 현재 pop 한 값을 max 값으로 변경한다.

 

2. 현재 입력받은 숫자가 stack의 top과 같은 경우

- 현재 top에 있는 값을 뽑아내기 때문에 "-"를 출력하고 top을 1 감소하면 된다.

 

3. 현재 입력받은 숫자가 stack의 top보다 작은 경우

- 임의의 수열을 만드는 것이 불가능하다. 현재 입력받은 숫자가 stack의 top보다 작다는 이야기는, 입력받은 숫자를 뽑아내기 위해서는 stack의 top에서부터 시작하여 현재 입력받은 숫자를 뽑아내야 한다. 그렇게 된다면 임의의 수열은 현재 stack의 top부터 입력받은 숫자까지 순서대로 주어져야 하는데 주어진 상황과 모순된 상황이 발생하게 된다..!

- 따라서 이럴 경우 NO를 출력하면 된다.

 

만약, 자바로 풀이를 시도하는 사람 중에 구현은 잘 한 것 같은데 출력 초과가 발생하는 경우는 BufferedWriter의 잘못된 사용 때문일 수 있다.

 

BufferedWriter의 기본 버퍼 크기는 16384byte라고 한다.

sb.append() 부분 대신 BufferedWriter를 사용하여 계속해서 bw.write를 하게 된다면 버퍼의 크기를 초과하게 되어서 BufferedWriter가 버퍼를 출력하고(비우고) 새로 버퍼를 채우게 된다.

따라서 NO를 출력해야 되는 경우에도 + 또는 -로 된 문자열을 출력될 수 있어서 출력초과라는 결과를 얻는 것 같다.

 

출력 초과를 해결하기 위해서는 2가지 방법이 있다.

 

1. StringBuilder 사용

2. 문자열 하나로 답을 만든 후 한 번에 BufferedWriter 출력

 

BufferedWriter의 버퍼 크기를 유의하면서 사용하면 문제 해결이 가능할 것이다.

 

 

3. 코드

import java.io.*;
import java.util.Scanner;

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        int[] stack = new int[100001];

        int top = 0;
        int max=0;


        for (int x = 0; x < num; x++) {
            int now = Integer.parseInt(br.readLine());

            if (now < stack[top]) {

                System.out.println("NO");
                return;

            } else if (now == stack[top]) {
                top--;
                sb.append("-\n");
            } else {

                for (int y = max+1; y <= now; y++) {
                    stack[++top] =y;
                    sb.append("+\n");
                }

                top--;
                max = now;
                sb.append("-\n");
            }

        }

        System.out.println(sb.toString());
        br.close();

    }

}