[BOJ 1874번] 스택 수열(Java)

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

1874번: 스택 수열

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

public class Main {
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb = new StringBuilder();
	static int[] stack;
	static int top=-1;
	
	public static void main(String args[]) throws Exception {
		int k=Integer.parseInt(br.readLine());
		int currentNum=1;
		stack=new int[k];
		for(int iter=0;iter<k;iter++) {
			int num=Integer.parseInt(br.readLine());
			if(num>=currentNum) {
				for(;currentNum<=num;currentNum++) {
					push(currentNum);
				}
				currentNum=num+1;
				pop();
			}
			else {
				if(num!=pop()) {
					System.out.println("NO");
					return;
				}
			}
		}
		System.out.println(sb);
	}
	
	static public void push(int num) {
		stack[++top]=num;
		sb.append("+\n");
	}
	
	static public int pop() {
		sb.append("-\n");
		if(top<0) return -1;
		else return stack[top--];
	}
	
	static public int size() {
		return top+1;
	}
	
	static public int empty() {
		if(top<0) return 1;
		else return 0;
	}
	
	static public int top() {
		if(top<0) return -1;
		return stack[top];
	}
}

 이 문제는 백준 10828번에서 사용했던 스택 함수들을 바탕으로 사용했습니다.

아래 링크와 제 풀이를 참고하실 분들은 참고해주시면 좋을 것 같습니다.

찾아보니 자바의 Stack 클래스라는 게 있어서 스택 함수들을 따로 구현하지 않아도 괜찮다고 합니다.

그래서 다음 번에는 Stack 클래스를 이용해서 문제를 풀어보도록 하겠습니다!

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

10828번: 스택

https://eloquence-developers.tistory.com/25

[BOJ 10828번] 스택 (Java)

 

 일단 숫자 k를 입력받았을 때, 1부터 k까지 모든 자연수를 한 번씩 사용해야 되고, push나 pop은 연속적으로 진행이 되어야 합니다.

 

먼저 push를 하는 경우를 살펴봅시다.

처음에 currentNum란 변수를 1로 지정해놓았는데요, 이 숫자는 스택에 들어갈 입력 대기 중인 숫자로 1부터 k까지 순차적으로 증가될 예정입니다.

currentNum이 입력받은 수 num보다 작거나 같을 때 push가 실행되는데요, currentNum이 입력받은 숫자 num까지 증가할 때까지 1씩 증가시키며 숫자를 차례대로 push 시킵니다.

currentNum이 num이 되면 pop을 실행시켜 최상단의 숫자 num이 스택에서 빠져나오고, 빠져나온 숫자는 StringBuilder sb에 저장이 됩니다.

 

pop을 하는 경우는 push를 하는 경우의 반대 경우인데요, 이 때 pop을 해서 나오는 숫자와 입력한 숫자 num이 같지 않으면 코드는 "NO"를 출력하고 코드를 종료합니다.

 

저는 이 문제를 풀면서 한 가지 에러가 났었습니다.

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

public class Main {
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static int[] stack;
	static String str="";
	static int top=-1;
	
	public static void main(String args[]) throws Exception {
		int k=Integer.parseInt(br.readLine());
		int currentNum=1;
		stack=new int[k];
		for(int iter=0;iter<k;iter++) {
			int num=Integer.parseInt(br.readLine());
			if(num>currentNum) {
				for(;currentNum<=num;currentNum++) {
					push(currentNum);
				}
				pop();
			}
			else {
				if(num!=pop()) {
					bw.write("NO");
					bw.flush();
					bw.close();
					return;
				}
			}
		}
		bw.write(str);
		bw.flush();
		bw.close();
	}
	
	static public void push(int num) {
		stack[++top]=num;
		str+="+\n";
	}
	
	static public int pop() {
		str+="-\n";
		if(top<0) return -1;
		else return stack[top--];
	}
	
	static public int size() {
		return top+1;
	}
	
	static public int empty() {
		if(top<0) return 1;
		else return 0;
	}
	
	static public int top() {
		if(top<0) return -1;
		return stack[top];
	}
}

 이 코드는 제가 초반에 작성했던 코드로 위의 코드와 로직 자체는 비슷합니다만, 틀렸다는 메시지를 받았습니다.

코드를 수정하다 보니 이유를 알게 되었는데요, 바로 StringBuilder를 쓰지 않았기 때문입니다.

그래서 이 문제를 푸시는 분들도 StringBuilder 객체를 사용하시면 좋을 것 같습니다.