[Gold IV] 오큰수 - 17298 - JAVA[자바]

문제 링크

성능 요약

메모리: 142136 KB, 시간: 1108 ms

분류

자료 구조, 스택

제출 일자

2023년 10월 14일 15:49:47

문제 설명

크기가 N인 수열 A = A₁, A₂, ..., A_N이 있다. 수열의 각 원소 A_i에 대해서 오큰수 NGE(i)를 구하려고 한다. A_i의 오큰수는 오른쪽에 있으면서 A_i보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -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의 원소 A₁, A₂, ..., A_N (1 ≤ A_i ≤ 1,000,000)이 주어진다.

출력

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

 

풀이

값을 읽어들이면서 정렬을 유지하는 Monotonic Stack을 활용하는 문제다.

맨 오른쪽부터 값Ai을 읽어들이면서  해당 원소보다 작은 값은 pop해주면서 스택의 정렬 상태를 유지해준다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Stack<Integer> stack = new Stack<>();
        // 값을 입력받은 뒤 뒤에서부터 읽어들임
        for (int i = N - 1; i >= 0; i--) {
        	값을 읽어옴
            int tmp = arr[i];

			// 스택이 비어있지 않고 stack의 top 값을 읽어서 tmp보다 작거나 같다면 pop
            // 오큰수는 Ai보다 큰 수기 때문에 작거나 같으면 빼줘야 함
            while (!stack.isEmpty() && stack.peek() <= tmp) {
                stack.pop();
            }
			
            // 만약 Stack이 비어있다면 Ai보다 큰 수는 없는 것이기 때문에 -1을 넣어준다.
            if (stack.isEmpty()) {
                arr[i] = -1;
            } 
            else {
            	// 비어있지 않다면 가장 top에 있는 숫자가 Ai보다 큰 수중 가장 왼쪽에 있는 값
                arr[i] = stack.peek();
            }
			// tmp 값을 넣어준다.
            stack.push(tmp);
        }

        for (int n : arr) {
            bw.write(n + " ");
        }
        bw.flush();
        bw.close();
    }
}

비슷하지만 다른 풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());;
        }

        /**
         * 스택이 비어있지 않으면서 현재 원소가 스택의 Top 원소보다 큰 경우 해당 조건을 만족할 때 까지 stack에서 pop 해당 인덱스의 값을 현재원소로 교체함
         * 
         * 쉽게 표현하면 스택에 들어있는 인덱스의 value를 가장 크면 바로 교체해주는 것임
         */
        for (int i = 0; i < N; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                arr[stack.pop()] = arr[i];
            }

            stack.push(i);
        }
        while (!stack.isEmpty()) {
            arr[stack.pop()] = -1;
        }

        for (int n : arr) {
            bw.write(n + " ");
        }
        bw.flush();
        bw.close();
    }
}