풀이
일단 문제를 이해하는데 오래걸렸다…문제를 잘 읽어봐야 한다. 1부터 n까지의 수를 스택에 일단 넣는다는 문장이 있다. 즉, 입력받은 수열대로 1부터 n까지의 스택에서 꺼내오려면 어떤 연산이 필요하냐는 것이다!!
예제 입력에서 처음 값인 4가 1부터 n까지의 오름차순 스택에서 나오려면, 일단 빈 스택에 1,2,3,4를 넣고 4를 빼야하기 때문에 ++++-가 나오는 것이다. 그리고, 그 상태에서 바로 3을 또 pop하기 때문에 -가 나온다.
그렇다면, 이 문제를 풀기 위해선 일단 입력받은 수열의 이번 차례 값과 현재 스택 상태를 비교해야 한다. 스택의 상태를 나타내는, 즉, 스택이 어떤 수까지 들어왔었는지를 체크하기 위해 flag변수를 사용하였다. 그리고 이 flag변수와 입력받은 수열을 순서대로 비교한다.
- flag <= 원소 : 스택에 수열에서 이번 차례인 값까지 push를 한다음에, pop을 해서 알맞은 원소 값을 가져온다.
- flag > 원소 : pop연산이 필요하다. 그런데 이 pop한 값이 수열에 나와있는 값보다 커버리면, 더이상 스택으로 이 수열을 만들 수가 없다!!
ex) 예제 입력 2를 보자.
1 2 5 까지의 진행 상황은 +-+-+++-이다. 이 상태에서의 스택은 3,4이다. 그런데 다음에 꺼내야하는 값은 3인 것이다. 스택은 후입선출이기 때문에 pop을 하면 4가 나온다. 즉, 이러한 수열은 스택으로 만들 수가 없다.
소스 코드
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
import java.util.*;
public class 스택수열 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Stack<Integer> stack = new Stack<>();
ArrayList<String> result = new ArrayList<>();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
int flag = 1;
for (int i = 0; i < n; i++) {
int now = arr[i];
if (now >= flag) {
while (now >= flag) {
stack.push(flag++);
result.add("+");
}
stack.pop();
result.add("-");
}
else {
int tmp = stack.pop();
if (tmp > now) {
System.out.println("NO");
System.exit(0);
break;
}
else {
result.add("-");
}
}
}
for (int i = 0; i < result.size(); i++) {
System.out.println(result.get(i));
}
}
}
태클 감사합니다.
조언 환영입니다.