boj)17298 - 오큰수
2020. 9. 15. 16:10ㆍPS/boj
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class boj_17298 {
static Stack<Integer> s = new Stack<>();
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] arr = new int[n];
int[] nge = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < arr.length; i++) {
if (s.isEmpty()) {
s.push(i);
}
// 현재의 값이 스택의 top보다 크다면 현재값이 오큰수
while (!s.isEmpty() && arr[i] > arr[s.peek()]) {
nge[s.pop()] = arr[i];
}
s.push(i); // 현재 값도 오큰수를 구해야하니 스택에 Push
}
// 위에 과정을 거쳤는데도 스택에 쌓여있다는것은 오큰수가 없다는 뜻
while (!s.isEmpty()) {
nge[s.pop()] = -1;
}
// 출력
for (int value : nge) {
sb.append(value).append(" ");
}
System.out.println(sb.toString());
}
}
- 어렵다,,,,
- 스택 생각
- 오큰수라는 것은 인덱스와 값이 크면서 인덱스가 제일 작은 값
- 그러니까 나 다음 첫번째에 등장하는 큰 수라고 생각
'PS > boj' 카테고리의 다른 글
boj)1929 - 소수 구하기 (0) | 2020.09.15 |
---|---|
boj)17299 - 오등큰수 (0) | 2020.09.15 |
boj)10799 - 쇠막대기 (0) | 2020.09.14 |
boj)17413 - 단어 뒤집기 2 (0) | 2020.09.14 |
boj)1158 - 요세푸스 문제 (0) | 2020.09.14 |