[문제]
https://www.acmicpc.net/problem/1874
[풀이]
1. 입력 받기
- 수열 길이 n을 입력받는다
- n개의 수열을 배열에 저장한다
2. 문제 적용
- stack: 숫자를 담을 stack
- current: 현재 push할 수 있는 숫자 (1부터 시작한다)
- result: 결과 연산을 저장하여 종료 시 보여주는 StringBuilder
3. 수열을 만들 수 있는지 체크
- 원하는 숫자가 나올때까지 push실행 +를 저장
- stack의 top(peek)한 숫자가 원하는 숫자라면 pop실행 -를 저장
- stack의 top값이 n개의 수열 배열에 존재하지 않는다면 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
|
public class stack001874 {
/**
* 백준 1874 스택 수열
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] sequence = new int[n];
for(int i = 0; i < n; i++){
sequence[i] = sc.nextInt();
}
/*
* 4 3 6 8 7 5 2 1 >> 만들어야하는 숫자
* 1 2 3 4 5 6 7 8 >> 실제로 들어오는 숫자
* 진행순서 >> 1, 2, 3, 4
* >> + + - -
* */
Stack<Integer> stack = new Stack<>();
StringBuilder result = new StringBuilder();
int current = 1;
boolean possible = true;
for(int i = 0; i < n; i++) { // 1 >> n번까지의 숫자가 순서대로 들어온다
int num = sequence[i];
// 만들어아햐난 수열의 n번째 숫자보다 작거나 같으면 +
while(current <= num) {
stack.push(current++);
result.append("+\n");
}
// 수열의 n번째 숫자와 현재 stack의 head숫자가 같다면 pop이후 -를 추가
if(stack.peek() == num) {
stack.pop();
result.append("-\n");
} else { // 아니라면 실패처리
possible = false;
break;
}
}
if(possible) {
System.out.println(result.toString());
} else {
System.out.println("NO");
}
}
}
|