[백준 JAVA] 17298번 풀이 - 오큰수 (인덱스 🥺..)

 

 

생각의 방향

스택을 이용하는 것은 알았으나, 스택에 무엇을 넣어야할지 갈피를 잡지 못하고 있었음....

"수열의 원소"를 넣을 생각만 하고, "인덱스"를 사용할 줄은 꿈에도 몰랐지....

인덱스 참 중요하구나.

 

1. 스택에는 수열(arr)의 원소의 인덱스가 들어간다. 
2. 오큰수 조건에 일치는 원소를 만나면, 스택에서 값을 꺼낸다. 오큰수를 만나지 않으면 스택에 인덱스 값이 유지된다. 

아래 그림은 예시 수열을 가지고 풀어서 정리한 내용이다! 

 

 

 

package quiz;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

/** 오큰수
 * 원소에 대한 오큰수 nge(i) 를 구하려고 한다.
 * 오큰수 = 원소의 오른쪽에 있으면서 원소 보다 큰 수 중에서 가장 왼쪽에 있는 수이다.
 * 그러한 수가 없는 경우 오큰수는 -1이다.
 * 가령 [3,5,2,7] 인 경우
 * nge(1) = 5, (5,2,7 중에서 가장 왼쪽. 5)
 * nge(2) = (2,7 중에) 1.큰수 2.가장 왼쪽 = 7
 * nge(3) = 1.큰 수 2.가장 왼쪽 7
 * nge(4) = 없음. -1
 *
 * 조건.
 * 1. 큰 수.
 * 2. 가장 왼쪽
 *
 */
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());
        int [] arr = new int[n];
        int [] result = new int[n];
        Stack<Integer> stack = new Stack<>();

        //수열의 원소가 들어간다.
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            result[i] = -1;
        }
        
        StringBuilder sb = new StringBuilder();

        for(int i=0; i<n; i++){
            while(!stack.isEmpty() && arr[stack.peek()] < arr[i]){
                result[stack.pop()] = arr[i];
            }
            stack.add(i); //처음에 비어있는 stack 에서는 첫번째 원소의 인덱스 0을 넣어준다.
        }

        for(int j : result){
            sb.append(j).append(" ");
        }
        System.out.println(sb);

    }
}