이번 문제는 스택을 사용하는 문제이다.
스택에 인덱스를 넣어주며 활용을 하면 되는데
예시를 들어서 설명을 하면 편할 것 같다.
3 2 5 8 이라는 배열이 있다고 하자.
스택에 먼저 첫 인덱스인 0을 넣어준다.
stack.push(0)
그 후 반복문을 돌며 해당 인덱스에 해당하는 값보다 더 큰 값을 찾으면 된다.
arr[stack.peek()] == arr[0] == 3
이고 저 값보다 더 큰 값을 가지는 것은 arr[1] == 5이다.
while(arr[stack.peek()] < arr[i]) {
result[stack.pop()] = arr[i]
}
로 표현할 수 있는데
배열을 하나하나 조사하며 해당 값보다 더 큰 값이 나오면 해당 값까지의 오큰수를 모두 arr[i]로 설정하는 것이다.
아래 자세한 코드를 보자
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int[] A = new int[N];
int[] result = new int[N];
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
stack.push(0);
for(int i = 1; i < N; i++) {
while(!stack.isEmpty() && A[stack.peek()] < A[i]) {
result[stack.pop()] = A[i];
}
stack.push(i);
}
while(!stack.isEmpty()) {
result[stack.pop()] = -1;
}
for(int i = 0; i < N; i++) {
sb.append(result[i] + " ");
}
System.out.println(sb);
}
}