백준 1874: 스택 수열(java)

문제

문제를 이해하기만 하면 스택을 사용해 쉽게 풀이할 수 있는 문제인 듯 하다.

 

예제를 기준으로 설명해 보자. 4를 입력받았을 때 1부터 4까지 스택에 오름차순으로 push하고, 이때 스택의 top에 만들어야 하는 수열의 요소인 4가 있으므로 pop한다. 다음으로 3이 입력되지만, 앞선 입력으로 3까지의 수는 이미 스택에 삽입된 바 있기 때문에 이번에는 1부터 3까지 오름차순으로 push하는 작업 없이 바로 스택 top에 3이 있는지 확인한다. top에 3이 있으므로 이를 pop하고 다음 입력으로 넘어간다. 6을 입력받아 이전에 삽입된 적 없는 5와 6을 push하고 위와 같은 과정을 반복해 주면 예제와 같은 출력이 완성된다.

 

도식적으로 표현하면 아래와 같다.

---

풀이

 

직전에 push한 요소의 다음 요소부터 오름차순으로 push해야 하므로, 어디까지 입력되었는지 표시할 변수 index를 사용한다.

if(index<num) {	//추가로 push해야 한다면
	for(int j=index+1; j<num+1; j++) {
		stack.push(j);
		sb.append("+").append("\n");
	}
	index=num;
}

num은 이번에 만들어야 할 배열의 수이고, index는 직전에 입력받은 수일 때(직전에 push된 값이므로 index+1부터 push 새로 push해야 한다), index가 num보다 작을 경우 지난 push에 이어 추가로 push해야 하므로 index+1부터 num까지 스택에 push해준 뒤 index를 num으로 변경하여 다음 push를 이어갈 수 있게 한다.

else if(stack.peek()!=num) {	//top의 요소가 입력값과 다를 경우 배열을 만들 수 없음
	System.out.println("NO");
	return;
}

이번에 입력받은 num이 이전에 push된 적 있어 새롭게 push할 필요가 없는 경우, top이 num과 다르다면 배열을 구성할 수 없으므로 NO를 출력하고 return으로 전체 반복문을 종료한다.

stack.pop();
sb.append("-").append("\n");

top이 num과 같을 경우 pop한다.

 

전체 코드

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		Stack<Integer> stack=new Stack<>();
		
		int n=Integer.parseInt(br.readLine());
		int index=0;
		for(int i=0; i<n; i++) {
			int num=Integer.parseInt(br.readLine());
			
			if(index<num) {
				for(int j=index+1; j<num+1; j++) {
					stack.push(j);
					sb.append("+").append("\n");
				}
				index=num;
			}
			else if(stack.peek()!=num) {
				System.out.println("NO");
				return;
			}
			
			stack.pop();
			sb.append("-").append("\n");
		}
		System.out.println(sb);
	}
}

BufferedReader와 StringBuilder를 사용해 풀이했다.