[백준] 17298번_오큰수_Java

Shin·2025년 11월 9일

17298번 Java 백준 스택 오큰수 자료구조 자바

백준

목록 보기

5/11

문제 링크 👉🏻 https://www.acmicpc.net/problem/17298

👀 문제 접근

오른쪽에 있는 큰 수 중 가장 왼쪽에 있는 수를 구한다.

크기가 N인 수열 $A$ = $A_1$ , $A_2$ , ..., $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

🔎 해결 방식

입력과 저장

배열 크기 n과 n개의 수를 arr 배열에 저장한다.
nge 각 원소의 오큰수를 저장한다. 해당 배열에는 오큰수가 없을 때를 대비하여 -1로 채워놓는다.
stack 을 선언하고 int배열이 저장되도록 한다. new int[] {오큰수, index} 형식으로 저장한다.

오큰수 구하기

배열 arr 를 순회한다.
스택이 비어있거나 스택의 탑이 현재 arr보다 작으면 stack 에 현재arr 값과 인덱스 값을 푸쉬한다.
스택에 값이 있고, 스택의 탑이 현재 arr 보다 크면 while 문을 실행한다.
- 스택을 팝한다. 팝한 값에는 arr값과 해당 값의 인덱스가 저장된다. 팝한 인덱스값을 nge 의 인덱스에 대입하여 해당 값을 arr 의 값으로 저장한다.
- 해당 while 문은 스택에 값이 존재하고, 스택의 탑이 현재 arr 값보다 클동안 실행된다.

출력

1 ≤ N ≤ 1,000,000 이므로 출력은 StringBuilder 를 사용하여 한 번에 출력하도록 한다.

그림으로 설명하면 다음과 같다

💻 구현 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<int[]> stack = new Stack<>();

        int n = Integer.parseInt(br.readLine());

        int arr[] = new int[n];
        int nge[] = new int[n];
        Arrays.fill(nge, -1);

        String[] input = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && stack.peek()[0] < arr[i]) {
                int[] peek = stack.pop();
                nge[peek[1]] = arr[i];
            }
            stack.add(new int[]{arr[i], i});

        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(nge[i] + " ");
        }
        System.out.println(sb);
    }
}