오큰수

백준 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)을 공백으로 구분해 출력한다.

	입력	출력
예제1	4	5 7 7 -1
	3 5 2 7
예제2	4	-1 8 8 -1
	9 5 4 8

풀이

수열을 스택에 넣는다.
스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수는 오큰수가 된다.
스택이 채워져 있거나 배열[인덱스] >배열[top]인 경우 pop한 인덱스를 이용하여 정답 배열에 오큰수를 저장한다. 반복.
현재 인덱스를 push하고 다음 인덱스로 넘어간다.
위 과정을 반복하고 남은 인덱스는 -1 저장.

예제 1번의 경우,

3	5	2	7

index = 0
스택이 비어있으므로 push
index = 1
5(배열[1]) > 3(배열[top])이므로 pop한 인덱스를 이용해 정답 배열에 오큰수 저장. 현재 인덱스 push
index = 2
2(배열[2]) < 5(배열[top]) 이므로 push
index = 3
7(배열[3]) > 2(배열[top]) 이므로 pop한 인덱스를 이용해 정답 배열에 오큰수 저장.
7(배열[3]) > 5(배열[top]) 이므로 pop한 인덱스를 이용해 정답 배열에 오큰수 저장. 현재 인덱스 push
남은 인덱스는 -1 저장

스택)

		2
0	1	1	3

정답 배열)

5	7	7	-1

예제 2번의 경우,

9	5	4	8

index = 0
스택이 비어있으므로 push
index = 1
현재 인덱스 push
index = 2
현재 인덱스 push
index = 3
8(배열[3]) > 4(배열[2])이므로 pop해서 저장.
8(배열[3]) > 4(배열[1])이므로 pop해서 저장.
현재 인덱스 push
남은 인덱스는 -1 저장

스택)

-1	8	8	-1

정답 배열)

		2
	1	1	3
0	0	0	0

소스

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		final int N = Integer.parseInt(br.readLine()); // 수열 크기
		int num [] = new int[N]; // 수열
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++)
			num[i] = Integer.parseInt(st.nextToken());
		Stack<Integer> stack = new Stack<>(); //인덱스를 담을 스택
		int result [] = new int[N]; //정답 배열
		
		for(int index = 0; index < N; index++) { //수열의 인덱스 0부터 N-1까지
			while(!stack.isEmpty() && num[index] > num[stack.peek()])
				result[stack.pop()] = num[index];
			stack.push(index);
		}
		while(!stack.isEmpty())
			result[stack.pop()] = -1;
		for(int n : result)
			bw.write(n + " ");
		
		bw.flush();
		bw.close();
	}
}