[Java] 17928. 오큰수

www.acmicpc.net/problem/17298

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.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class BOJ_17298 {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static int[] result;
	public static void main(String[] args) throws Exception {
		StringBuilder sb = new StringBuilder("");
		int N = Integer.parseInt(in.readLine());
		result = new int[N];
		Stack<int[]> stack = new Stack<>();
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		for (int i = 0; i < N; i++) {
			if(stack.isEmpty())  {
				stack.add(new int[] {i, Integer.parseInt(st.nextToken())});
				continue;
			}
			int tmp = Integer.parseInt(st.nextToken());
			while(!stack.isEmpty() && stack.peek()[1] < tmp) {
				result[stack.pop()[0]] = tmp;
			}
			stack.add(new int[] {i, tmp});
			
		}
		while(!stack.isEmpty()) {
			int tmp[] = stack.pop();
			result[tmp[0]] = -1;
		}
		for (int tmp : result) {
			sb.append(tmp).append(" ");
		}
		sb.setLength(sb.length()-1);
		System.out.println(sb);
	}

}

이전에 송전탑? 관련 문제를 백준에서 푼 적이 있는데 방향이 반대인 문제였던 것 같다.

스택을 이용하여 해결해야 한다는 부담감에 고민하는 시간이 다소 걸렸던 것 같다.

다양한 문제를 접해봐야 한다고 생각하는 하루였다.