백준 1874번: 스택 수열

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

1874번: 스택 수열

1부터 n까지의 수를 스택에 넣었다가(push) 뽑아서(pop) 입력된 수열을 만드는 문제이다.

스택에 push할 때 +, pop할 때 -를 출력하고 수열을 만들지 못한다면 NO를 출력한다.

스택에 push할 때는 오름차순으로 입력받는다.

 

문제가 글만보고는 이해하기 힘들어서 예제를 직접 글로 써보면서 이해를 했다.

 

우선 수열을 배열에 넣어주고, 각 수열의 수가 pop될 때 break해서 다음으로 넘어가도록 만들어 주었다.

일단, 입력받은 적이 없는 수가 나오면 그 수까지 Stack에 입력받아준다.

그 뒤에 Stack의 맨 위의 수와 현재 반복문에서 가리키는 수열의 수가 같다면 pop해주고 다음 수열의 수로 넘어간다.

만약, 이 과정이 이루어질 수 없다면 break Label로 아예 탈출해서 NO를 출력해준다.

 

아래는 그렇게 하여 만든 코드이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    int N = Integer.parseInt(br.readLine());
    int elem = 0, idx = 0;
    Stack<Integer> stack = new Stack<>();
    int[] arr = new int[N];

    for (int i = 0; i < N; i++)
      arr[i] = Integer.parseInt(br.readLine());


    Label: for (int i = 0; i < N; i++) {
      while (true) {
        if (elem < arr[i]) {
          stack.push(++elem);
          bw.write("+\n");
        } else if (stack.peek() == arr[i]) {
          stack.pop();
          bw.write("-\n");
          break;
        } else {
          bw = new BufferedWriter(new OutputStreamWriter(System.out));
          bw.write("NO");
          break Label;
        }
      }
    }

    br.close();
    bw.flush();
    bw.close();
  }
}

이 코드를 제출하니까 출력 초과가 나왔다.

완전 틀리지는 않았지만 출력의 어떠한 문제가 있다는 의미로 받아들이고 생각을 했다.

근데 이 코드에서는 BufferedWriter로 출력하니까 이것에 어떤 문제가 있을 것 같았다.

찾아보니 BufferedWriter의 write는 문자열을 버퍼에 담아두었다가 flush로 한 꺼번에 출력하는 식인데,

이때, write로 모아둘 때 버퍼를 넘어가면 바로 출력되는 듯하다.

그렇다면 코드가 실행되는 도중에 버퍼가 쌓인 게 출력되다보니 오류가 생긴게 아닐까 싶다.

그래서 write로 쌓아두는 게 아니라 StringBuilder로 모으고 출력하는 것으로 코드를 바꿔주었다.

 

StringBuilder로 모으기만 하고 출력은 여전히 BufferedWriter를 사용했지만, 다행히 문제를 풀 수 있었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    int N = Integer.parseInt(br.readLine());
    int elem = 0;
    Stack<Integer> stack = new Stack<>();
    int[] arr = new int[N];

    for (int i = 0; i < N; i++)
      arr[i] = Integer.parseInt(br.readLine());

    Label: for (int i = 0; i < N; i++) {
      while (true) {
        if (elem < arr[i]) {
          stack.push(++elem);
          sb.append("+\n");
        } else if (stack.peek() == arr[i]) {
          stack.pop();
          sb.append("-\n");
          break;
        } else {
          sb = new StringBuilder("NO");
          break Label;
        }
      }
    }

    br.close();
    bw.write(sb + "");
    bw.flush();
    bw.close();
  }
}

문제 풀이와 별개로 if - else 구문을 어디서 본 형태로 따라해보았다.

} 만으로 코드가 한 줄 늘어나던 게 좀 줄어서 좋은 거 같다가도,

코드가 뭉쳐있는 느낌이라 가독성이 떨어지는 거 같기도 해서 좀 더 써보면서 정해야겠다.