[백준] 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이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

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

---

처음에는 orign과 nge를 모두 stack으로 했다가 시간초과가 나서, origin은 배열로 바꿨다.

배열의 맨 끝부터 for문을 돌며 nge를 찾는다.

nge에 있는 수가 origin[i]보다 작으면 pop하고 모두 pop한 후 nge가 비어 있으면 오큰수는 존재하지 않는 것을 의미한다.

그렇게 해서 nge의 top(peek)가 origin[i]보다 크면 i번째 수의 오큰수가 그 top이 된다.

처음에는 nge보다 작은 수를 모두 pop하는 게, 다음 수를 검사하는 것에 영향을 주지 않을까 생각했는데, 어차피 i번째수보다 i+1, i+2.. 번쨰 수가 작다면, i-1의 오큰수는 i번째 수가 될 것이므로 작은 수를 pop하는 것은 문제가 없다.

package Gold.g4;

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

public class BOJ_17298_오큰수stack {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] result = new int[N];
		int[] origin = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++)
			origin[i] = Integer.parseInt(st.nextToken());
		Stack<Integer> nge = new Stack<>();

		for (int i = N - 1; i >= 0; i--) {
			int n = origin[i];

			while (!nge.isEmpty() && nge.peek() <= n) // nge가 비어있지 않고 nge의 peek가 n보다 작거나 같으면 pop
				nge.pop();
			if (nge.isEmpty()) // pop한 후에 nge가 비어있으면 -1
				result[i] = -1;
			else if (nge.peek() > n) { // peek가 크면 오큰수
				result[i] = nge.peek();

			}

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

}