[백준] 스택, 큐 - 17298_오큰수 Java[자바]

 

이번 문제는 스택을 사용하는 문제이다.

 

스택에 인덱스를 넣어주며 활용을 하면 되는데

 

예시를 들어서 설명을 하면 편할 것 같다.

 

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);
    }
}