[백준_1874] 스택 수열(Stack)

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

1874번: 스택 수열

---

풀이

문제에 대한 이해가 필요하다. 첫 줄에는 스택에 push될 요소의 갯수를 입력받고, 두번째 줄 부터 마지막 번째 줄 까지는 스택에 저장되어 있는 해당 요소들이 pop되는 순서를 의미한다(여기서 스택에 저장되는 요소는 1부터 n까지의 값이 들어간다) 예를 들어 4 4 3 2 1 이라면 총 4개의 요소가 1->2->3->4 순서로 입력되고, 4->3->2->1 번 순서로 스택에서 pop되게 하는 것이 가능한지 확인하여 출력하는 것이다.

 

1. 현재 스택의 상태 확인

=> 현재 스택이 비어있는 경우 요소를 비교할 수 없기 때문에 현재까지 입력된 값에서 +1 값을 push해준 후 "+" 연산을 더해준다.

현재 스택에 데이터가 있는 경우 가장 마지막에 입력된 값을 저장(top)하여 pop해야 하는 요소(curVal)와 비교한다.

 

2. 입력받은 숫자(curVal) 확인

=> 입력받은 숫자의 값이 1) 이미 스택에서 push된 요소(top > curVal)인지, 2) push가 안된 요소(top < curVal)인지, 3) pop되어야 하는 요소(top == curVal)인지 확인한다.

1)의 경우 입력받은 숫자가 위치한 곳이 스택의 가장 마지막이 아니라는 의미이므로 해당 요소를 pop하기 위해서는 다른 값을 먼저 pop해야 한다. 즉, 입력 받은 순서대로 수열을 만들수 없다는 의미가 되므로 NO를 출력한다. flag를 추가하여 3번에서 그전에 입력된 요소에 대해 출력을 안하도록 구분하였다.

2)의 경우 push가 되어야 pop이 가능하므로 스택에 현재까지 입력된 값에서 +1 값을 push해준 후 "+" 연산을 더해준다.

3)의 경우 pop 연산을 해준 후 "-" 연산을 더해준 다음, 다음 요소 값으로 비교 값을 옮겨준다(curVal = b.get(++pivot))

 

3. 전체 요소에 대해 push와 pop이 완료되면 그동안 저장한 연산을 출력해준다.

소스코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		Stack<Integer> stack = new Stack<>();
		int a = Integer.parseInt(in.readLine());
		List<Integer> b = new ArrayList<>();
		StringBuilder str = new StringBuilder();
		boolean flag = true;
		
		for(int i=0; i<a; i++) {
			b.add(Integer.parseInt(in.readLine()));
		}
		
		int index = 1;
		int pivot = 0;
		int curVal = b.get(pivot);
		int top = 0;

		while(true) {
			if(stack.isEmpty()) {
				stack.push(index++);
				str.append("+\n");
				continue;
			}
			else
				top = stack.peek();
			
			if(top < curVal) {
				stack.push(index++);
				str.append("+\n");
			} else if (top == curVal) {
				stack.pop();
				str.append("-\n");

				if(pivot+1 == a)
					break;
				
				curVal = b.get(++pivot);
			} else {
				System.out.println("NO");
				flag = false;
				break;
			}
		}
		
		if(flag) 
			System.out.println(str);
	}
}