[Java] 17298 오큰수

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

 

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

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 num = Integer.parseInt(br.readLine());
        int[]arr = new int[num];
        int[]ans = new int[num];
        String[] str = br.readLine().split(" ");
        
        for(int i=0; i<num; i++){
            arr[i] = Integer.parseInt(str[i]);
        }
        Stack<Integer> myStack = new Stack<>();
        myStack.push(0);
        
        for(int i=1; i<num; i++){
            while(!myStack.isEmpty() && arr[myStack.peek()] < arr[i]){
                ans[myStack.pop()] = arr[i];
            }
            myStack.push(i);
        }
        while(!myStack.empty()){
            ans[myStack.pop()] = -1;
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        for(int i=0; i<num; i++){
            bw.write(ans[i] + " ");
        }
        bw.write("\n");
        bw.flush();
    }
}

▶ int num = Integer.parseInt(br.readLine()) : 수열의 개수를 입력받아 num 변수에 저장함

▶ int[]arr = new int[num] : 수열 배열을 저장할 arr 배열 선언

▶ int[]ans = new int[num] : 정답 배열을 저장할 ans 배열 선언

▶ String[] str = br.readLine().split(" ") : 공백으로 구분해 값을 입력받아 str 배열에 저장

▶ for(int i=0; i<num; i++){ arr[i] = Integer.parseInt(str[i]) } : 입력받은 값이 String형이기 때문에 Integer형으로 변환해 arr 변수에 값을 저장함

▶ Stack<Integer> myStack = new Stack<>() : Integer 형으로 구성된 myStack 스택 선언

▶ myStack.push(0) : 처음에는 스택이 비어 있기 때문에 최초 값을 push해서 초기화함

 

for(int i=1; i<num; i++){
    while(!myStack.isEmpty() && arr[myStack.peek()] < arr[i]){
        ans[myStack.pop()] = arr[i];
    }
    myStack.push(i);
}

▶ 수열의 개수만큼 반복하여 myStack이 비어있지 않고 현재 수열의 값이 top에 해당하는 수열보다 클 때까지 pop()하고 정답 배열에 오큰수를 현재 수열로 저장함

▶ 현재 수열을 스택에 push() 해줌

 

▶ while(!myStack.empty()){ ans[myStack.pop()] = -1 } : myStack이 빌 때까지 스택에 있는 인덱스의 정답 배열에 -1을 저장함

▶ for(int i=0; i<num; i++){ bw.write(ans[i] + " ") } : 정답 배열을 출력함