알고리즘65 :: BOJ_17298_오큰수
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class {
static int n;
static int[] arr;
static int[] oce;
public static void main(String[] args) throws Exception{
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new int[n];
oce = new int[n];
String[] temp = br.readLine().split(" ");
for(int i=0; i<n; i++) {
arr[i] = Integer.parseInt(temp[i]);
}
Stack<Integer> sta = new Stack<>();
sta.push(0);
for(int i=1; i<n; i++) {
if(sta.isEmpty()) {
sta.push(i); //넣어야 비교할 대상이 생긴다.
}
while(!sta.isEmpty() && arr[sta.peek()]<arr[i]) {
oce[sta.pop()] = arr[i];
}
sta.push(i);
}
while(!sta.isEmpty()) {
oce[sta.pop()] = -1;
}
for(int i=0; i<oce.length; i++)
System.out.print(oce[i]+" ");
System.out.println();
}
}
|
cs |
오큰수 문제는
6
2 1 2 1 7 8
7 2 7 7 8 -1
실행 동작은 다음과 같다.
int[ ] arr = { 2, 1, 2, 1, 7, 8 }
일때 Stack에 index 0 이 들어간다.
현재 스택 : 0
다음 index와 비교 -> index 1 의 값 1은 현재스택 index 0 (=2) 보다 값이 작으므로 안된다.
이런식으로 다음 index 의 값 2, 그 다음 index 의 값 1 해당하지 못하고
7 일때 해당되므로 현재스택 은 비어지고 오큰수를 저장하는 배열에 7이 들어가게 된다.
이런식으로 반복하면 해결할 수 있다.