1874번: 스택 수열
1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.
www.acmicpc.net
스택에 1~N을 순서대로 push, pop 과정을 반복하면서 입력에 주어진 순서대로 pop을 할 수 있는지 출력하는 문제입니다.
아래의 예시를 이용하여 리뷰하겠습니다.
8
4
3
6
8
7
5
2
1N = 8, list[] = {4, 3, 6, 8, 7, 5, 2, 1} 입니다.
push 1 -> s.peek = 1, list[idx] = 4 (s.peek != list[idx] 이므로 (+))
push 2 -> s.peek = 2, list[idx] = 4 (s.peek != list[idx] 이므로 (+))
push 3 -> s.peek = 3, list[idx] = 4 (s.peek != list[idx] 이므로 (+))
push 4 -> s.peek = 4, list[idx] = 4 (s.peek == list[idx] 이므로 (-)후에 idx++)
s.peek = 3, list[idx] = 3 (s.peek == list[idx] 이므로 (-)후에 idx++)
s.peek = 2, list[idx] = 6 (s.peek != list[idx] 이므로 다음 진행)
push 5 -> s.peek = 5, list[idx] = 6 (s.peek != list[idx] 이므로 (+))
push 6 -> s.peek = 6, list[idx] = 6 (s.peek == list[idx] 이므로 (-)후에 idx++)
s.peek = 5, list[idx] = 8 (s.peek != list[idx] 이므로 다음 진행)
push 7 -> s.peek = 7, list[idx] = 8 (s.peek != list[idx] 이므로 (+))
push 8 -> s.peek = 8, list[idx] = 8 (s.peek == list[idx] 이므로 (-)후에 idx++)
s.peek = 7, list[idx] = 7 (s.peek == list[idx] 이므로 (-)후에 idx++)
s.peek = 5, list[idx] = 5 (s.peek == list[idx] 이므로 (-)후에 idx++)
s.peek = 2, list[idx] = 2 (s.peek == list[idx] 이므로 (-)후에 idx++)
s.peek = 1, list[idx] = 1 (s.peek == list[idx] 이므로 (-)후에 idx++)
여기서 8까지 push 완료하였고, 스택 안의 모든 숫자가 pop되었으므로 순서대로 출력해주시면 됩니다.
만약에 모든 push가 이루어졌는데 pop이 더이상 진행되지 못할 경우에는 NO를 출력해주셔야합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static Stack<Integer> s = new Stack<>();
static int list[];
static int N;
static void func() {
int idx = 0;
for (int i = 1; i <= N; i++) {
s.add(i);
sb.append("+\n");
while (!s.isEmpty() && idx < N && s.peek() == list[idx]) {
s.pop();
sb.append("-\n");
idx++;
}
}
while(!s.isEmpty() && idx < N && s.peek() == list[idx]) {
s.pop();
sb.append("-\n");
idx++;
}
if(!s.isEmpty()) {
sb = new StringBuffer();
sb.append("NO\n");
}
System.out.println(sb.toString());
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
list = new int[N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
list[i] = Integer.parseInt(st.nextToken());
}
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > data-structure' 카테고리의 다른 글
| boj 2504 괄호의 값 (0) | 2021.01.26 |
|---|---|
| boj 6198 옥상 정원 꾸미기 (0) | 2021.01.26 |
| boj 17298 오큰수 (0) | 2021.01.25 |
| boj 4358 생태학 (0) | 2021.01.25 |
| boj 5639 이진 검색 트리 (0) | 2021.01.24 |