[백준] 17298 오큰수 - JAVA

문제

크기가 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이다.

https://www.acmicpc.net/problem/17298

17298번: 오큰수

 

접근 방법

자신의 오른쪽에 있는 큰 수 중에 가장 가까운 수가 오큰수인데 이를 반대로 생각하면 좀 더 쉽게 접근할 수 있습니다.

자신이 오큰수가 되는 경우를 살펴보는 것입니다. 즉 자신의 왼쪽에 있는 수 중 자신보다 큰 수를 만나기 전까지의 수들에게는 자신이 오큰수가 됩니다. 만약 자신보다 작은 수지만 이미 오큰수가 있다면 오큰수가 될 수 없습니다.

 

A = [3, 5, 2, 7]인 경우를 살펴보겠습니다.

오큰수를 저장하는 배열을 result라고 할 때

3이 첫번째 숫자이기 때문에 오큰수가 될 수 없습니다.

5는 3보다 크기때문에 result[0] = 5 입니다.

2는 바로 자신보다 큰 수인 5를 만나기 때문에 오큰수가 될 수 없습니다.

7은 2, 5의 오큰수가 될 수 있고(result[2] = 7, result[1] = 7), 3은 이미 오큰수 5가 있기 때문에 3의 오큰수는 될 수 없습니다. 

결과적으로 result = {5, 7, 7, -1} 가 됩니다.

 

이 과정을 스택을 이용하면 편하게 구현할 수 있습니다.

스택에는 값의 인덱스를 순서대로 push합니다. 스택에 이미 들어간 값은 나보다 왼쪽에 있는 값의 인덱스입니다. 즉 스택에 있는 인덱스에 해당하는 값이 나보다 작다면 내가 오큰수가 되기 때문에 stack에서 pop하여 자신을 오큰수로 저장합니다.

아래는 전체 코드입니다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int[] input = new int[n];
		int[] result = new int[n];
		for(int i=0; i<n; i++) {
			input[i] = Integer.parseInt(st.nextToken());
			result[i] = -1;
		}
		
		Stack<Integer> stack = new Stack<>();
		for(int i=0; i<n; i++) {
			while(!stack.isEmpty() && input[stack.peek()] < input[i]) {
				result[stack.pop()] = input[i];
			}
			stack.push(i);
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<n; i++)
			sb.append(result[i]+" ");
		System.out.println(sb);
	}
}