[백준 1874/Java] 스택 수열

문제

---

1874번: 스택 수열

 

풀이 과정

---

이 문제를 풀면서 가장 많이 본 에러가 출력 초과였습니다. 원인은 BufferedWriter에 있었습니다.

문제를 보시면 입력된 수열을 만들 수 있다면 +,-로 표현하고 불가능한 경우에는 NO를 출력해야 합니다.

BufferedWriter의 flush는 직접 호출하지 않아도 출력 양이 내부 버퍼의 크기를 초과하면 자동으로 호출됩니다.

그렇기에 n의 값이 커져서 Buffer에 입력된 값들이 많아지면 한번 +,-를 출력합니다.

물론 정답이 NO가 아니라면 상관없지만 NO가 되야하는 경우 문제가 발생합니다.

이문제를 해결하기 위해서 StringBuilder를 사용하시는 것을 추천드립니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	static int stack[] = new int[100000];
	static int point = -1;
	
	public static void push(int num) {
		stack[++point] = num;	
	}
	
	public static int pop() {
		if(point < 0) {
			return -1;
		}
		return stack[point--];
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		int current_num = 1;  //1~n까지 오름차순
		int idx = 0;          //입력 배열의 인덱스
		int n_arr[] = new int[n]; //입력 배열
		for(int i=0; i<n; i++) {
			n_arr[i] = Integer.parseInt(br.readLine());
		}
		
		while(current_num <= n) {
			if(current_num == n && point == -1) {  //스택에 들어갈 숫자가 n과 같고 다음에 더 이상 들어갈 숫자가 없다면, 1~n까지 오름차순으로 입력된 경우
				sb.append("+\n");
				sb.append("-");
				System.out.println(sb);
				br.close();
				System.exit(0);
			}
			if(current_num == n_arr[idx]) {   //push와 pop을 둘 다 해야하는경우
				sb.append("+\n");
				sb.append("-\n");
				push(current_num);
				pop();
				current_num++;
				idx++;	
			}
			else if(current_num > n_arr[idx]) {  
				sb.append("-\n");
				int popNum = pop();
				if(popNum != n_arr[idx]) {
					System.out.println("NO");
					br.close();
					System.exit(0);
				}
				idx++;
			}
			else {
				sb.append("+\n");
				push(current_num);
				current_num++;
			}
		}
		
		while(idx < n) { //n_arr에 남은 숫자들은 내림차순이어야 한다
			if(idx == n-1) {
				sb.append("-");
				break;
			}
			if(n_arr[idx] < n_arr[idx+1]) {
				System.out.println("NO");
				br.close();
				System.exit(0);
			}
			else {
				sb.append("-\n");
				idx++;
			}
		}
		System.out.println(sb);
		br.close();
	}
}

이 문제를 풀면서 생각했던 No가 나와야하는 상황들

• current_num의 값이 n값과 같아져서 push, pop을 한 상태이면 나머지 뒤에 나올 n_arr값들은 내림차순 순이어야 합니다. (문제의 예제 입력 2 참고)
• current_num의 값이 n_arr[idx]값보다 큰 경우 stack에서 pop을 한 뒤 이 pop 값이 n_arr[idx] 값과 다른 경우

예를 들어, n = 10, n_arr = {4,3,7,8,2,9,10,6,5,1}라고 하겠습니다.

이 경우 +1 +2 +3 +4 -4 -3 +5 +6 +7 -7 +8 -8 이다음에서 예외가 발생합니다. current_num 값은 9이고, n_arr[idx] 값은 2입니다. 이 경우에는 stack에서 pop을 해야 하는데, pop을 한 값은 6이 되므로 NO를 출력해야 합니다.