BOJ - 1874 스택 수열

1874 스택 수열 : https://www.acmicpc.net/problem/1874

---

Problem

---

Solve

Stack에 들어있는 수를 pop하여 주어진 수열을 만들수 있는지 확인하는 문제.

문제 풀이는 아래와 같다.

1. stack.push()는 오름차순으로 한다고 했으니 1부터 N까지의 수를 stack에 push한다.
2. 각 수를 push한 후 stack.peek()값이 주어진 수열의 값에 만족한다면 만족하지 않을 때까지 pop()을 반복한다.
3. N까지의 모든 수를 stack에 push했을 때 stack에 남아있는 수가 있다면 주어진 수열을 만족하지 못한 것이기 때문에 "NO"를 반환한다.
   그렇지 않다면 push,pop 때 저장한 결과를 반환한다.
   

---

Code

public class 스택수열 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		int[] sequence = new int[N];
		for (int i = 0; i < N; i++) {
			sequence[i] = Integer.parseInt(br.readLine());
		}

		StringBuilder sb = new StringBuilder();
		Stack<Integer> stack = new Stack<>();
		int i=0;
		for (int n = 1; n <= N; n++) {
			stack.push(n);
			sb.append("+");
			sb.append("\n");

			//stack.peek()와 주어진 수열값이 같을 동안 pop()
			while(!stack.isEmpty() && stack.peek() == sequence[i]){
				stack.pop();
				sb.append("-");
				sb.append("\n");
				i++;
			}
		}
        //stack에 값이 존재한다면 주어진 수열을 만들 수 없다는 뜻.
		if(!stack.isEmpty()){
			sb = new StringBuilder();
			sb.append("NO");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

---

Result

---

Reference