BOJ(백준 온라인 저지) 1874번 with 자바[JAVA]

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

1874번: 스택 수열

---

 

우선 문제를 읽자 마자 들었던 생각은

"도데체 뭔 소리지?"

였었다.

 

예시를 들며 스택 수열을 설명하겠다.

 

예제 입력 1과 같이 n이 8이 나왔다고 가정하자.

입력	스택	결과 수열	출력
8	stack = {}	result = {}
4	stack = {1}	result = {}	+(push)
	stack = {1, 2}	result = {}	+(push)
	stack = {1, 2, 3}	result = {}	+(push)
	stack = {1, 2, 3, 4}	result = {}	+(push)
	stack = {1, 2, 3}	result = {4}	-(pop)
3	stack = {1, 2}	result = {4, 3}	-(pop)
6	stack = {1, 2, 5}	result = {4, 3}	+(push)
	stack = {1, 2, 5, 6}	result = {4, 3}	+(push)
	stack = {1, 2, 5}	result = {4, 3, 6}	-(pop)
8	stack = {1, 2, 5, 7}	result = {4, 3, 6}	+(push)
	stack = {1, 2, 5, 7, 8}	result = {4, 3, 6}	+(push)
	stack = {1, 2, 5, 7}	result = {4, 3, 6, 8}	-(pop)
7	stack = {1, 2, 5}	result = {4, 3, 6, 8, 7}	-(pop)
5	stack = {1, 2}	result = {4, 3, 6, 8, 7, 5}	-(pop)
2	stack = {1}	result = {4, 3, 6, 8, 7, 5, 2}	-(pop)
1	stack = {}	result = {4, 3, 6, 8, 7, 5, 2, 1}	-(pop)

 

이처럼 주어진 수가 스택의 top에 있는 수보다 크면

top에 있는 수에서 오름차순으로 push하여 스택에 채워넣고,

pop을 하여 원하는 수를 꺼내온다.

 

만약 원하는 수가 top에 있는 수라면 그냥 pop하여 원하는 수를 꺼내온다.

 

지금까지 스택수열이 가능한 경우였고,

NO인 경우는 어떨까? 예제 입력 2를 보자

 

입력	스택	결과 수열	출력
5	stack = {}	result = {}
1	stack = {1}	result = {}	+(push)
	stack = {}	result = {1}	-(pop)
2	stack = {2}	result = {1}	+(push)
	stack = {}	result = {1, 2}	-(pop)
5	stack = {3}	result = {1, 2}	+(push)
	stack = {3, 4}	result = {1, 2}	+(push)
	stack = {3, 4, 5}	result = {1, 2}	+(push)
	stack = {3, 4}	result = {1, 2 ,5}	-(pop)
3	error!! 스택에서 pop할 수 없는 수(스택의 top에는 4가 있기 때문에)		NO

이처럼 스택에서 pop할수 없는 수를 입력으로 받는 다면 NO를 출력하면 된다.

 

코드를 보자.

 

 

 

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());
        // 스택에 추가할 수, 0부터 시작해서 n까지
		int n = 0;
		
		for(int i=0; i<N; i++) {
			
			int target = Integer.parseInt(br.readLine());
			
            // 만약 꺼내야할 수가 n보다 크다면, n을 증가시키며 stack에 push해야함
			if(n < target) {
				
                // n이 target이 될때까지 stack에 push
				while(n < target) {
					
					stack.add(++n);
                    // push할때마다 +를 StringBuilder에 append
					sb.append("+").append("\n");
				
				}
				
				stack.pop();
				sb.append("-").append("\n");
			
            // 만약 꺼내야할 수가 n보다 작다면, stack의 top을 봐야함
			}else {
				
                // stack의 top이 target과 다르면 false, top이 target과 같다면 true
				boolean found = false;
				
				if(!stack.isEmpty()) {
					
					int top = stack.pop();
					sb.append("-").append("\n");
					// top과 target이 같으면 true
                    
                    			if(top == target)
						found = true;
					
				}
				
                // found가 false일때는 top과 target이 다르다는 뜻 -> NO
                
				if(!found) {
					
					System.out.println("NO");
					return;
					
				}
				
			}
			
		}
		System.out.print(sb);
 	}
}