Question
문제 해설
- 스택 : 후입선출
- 1~n까지의 수를 오름차순으로 하나씩 스택에 넣으면서 수열을 만듬
- 임의의 수열이 존재했을 때, push, pop 연산을 통해서 그 수열을 만들 수 있는지 출력
Solution
풀이 접근 방법
- 스택 = 순서대로 쌓여있음 -> 두번 빼서 가져올 수 없음
- 어디다가 뺀 값들을 가지고 있을 수 없음 => 수열 못 만들어짐
정답 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Main{
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.valueOf(br.readLine());
Stack<Integer> stack = new Stack<Integer>();
Queue<Integer> input = new LinkedList<Integer>();
StringBuilder answer = new StringBuilder();
int progressNum = 1;
for (int i = 0; i < N; i++) {
input.add(Integer.valueOf(br.readLine()));
}
while (!input.isEmpty()) {
int value = input.poll();
if (progressNum <= value) {
while (progressNum <= value) {
answer.append("+\n");
stack.add(progressNum++);
}
answer.append("-\n");
stack.pop();
} else {
if (stack.peek() == value) {
answer.append("-\n");
stack.pop();
} else {
answer = new StringBuilder("NO");
break;
}
}
}
bw.write(answer.toString() + "\n");
bw.flush();
bw.close();
}
}