[BaekJoon] 17298 오큰수 (Java)

1.  문제 링크

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

2.  문제

요약

• 크기가 N인 수열 $A = A_1, A_2, A_3, ...., A_N$이 있고 수열의 각 원소 $A_i$에 대해서 오큰수 NGE(i)를 구하려고 합니다.
• $A_i$의 오큰수는 오른쪽에 있으면서 $A_i$보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미합니다. 그러한 수가 없는 경우 오큰수는 -1입니다.
• N개의 수가 주어졌을 때, NGE(1), NGE(2), ..., NGE(N)을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000,000보다 작거나 같은 수열 A의 크기 N이 주어지고 두 번째 줄에 1보다 크거나 같고 1,000,000보다 작거나 같은 수열 A의 원소 $A_1, A_2, ..., A_N$이 주어집니다.
• 출력: 총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 출력합니다.

3.  소스코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static int[] series;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		series = new int[N];
		for(int i = 0; i < N; i++) {
			series[i] = scanner.nextInt();
		}
	}
	
	static void solution() {
		Stack<Integer> stack = new Stack<>();
		for(int i = 0; i < N; i++) {
			while(!stack.isEmpty() && (series[stack.peek()] < series[i])) series[stack.pop()] = series[i];
			stack.push(i);
		}
		while(!stack.isEmpty()) series[stack.pop()] = -1;
		for(int i = 0; i < N; i++) sb.append(series[i]).append(' ');
		System.out.println(sb.toString());
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

4.  접근

• 수열의 각 수들을 탐색하면서 현재 수열의 수가 이전의 수열의 수보다 작으면 Stack에 현재 수열의 수에 해당하는 index를 넣습니다.
• 그러다 만약 현재 수열의 수가 Stack에서 꺼낸 수를 index로 하는 수열의 수보다 크다면 Stack의 원소를 꺼내서 삭제하고 Stack에서 꺼낸 수를 index로 하는 수열의 수를 현재 수열의 수로 변경합니다.
• 모든 수열의 수에 대해 탐색하였는데 아직 Stack에 수가 남아있다면 이 수들은 자신보다 큰 수를 자신의 오른쪽에서 만나지 못했다는 뜻이므로 Stack에 남아있는 수들을 index로 하는 수열의 수를 -1로 변경합니다.