17298. 오큰수 (자바, Java)

아직 골드문제는 너무 어렵다. 풀이를 참고함.

스택에 값을 저장하는게 아니라, 스택에 index를 저장하는 방법으로 풀이.

더 큰값이 나오는 경우, 오큰수로 해당 index를 pop하여 오큰수로 배열값을 덮어씌운다.

스택이 비었다면, 오큰수가 없으므로 -1을 넣어준다.

 

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String[] str = br.readLine().split(" ");
		int[] a = new int[n];
		Stack<Integer> stack = new Stack<>(); // 배열의 index를 담을 스택.
		for (int i=0; i<n; i++) {
			a[i] = Integer.parseInt(str[i]);
		}
		
		StringBuilder sb = new StringBuilder();
		
		for (int i=0; i<n; i++) {
			while (!stack.isEmpty() && a[i]>a[stack.peek()]) {
				a[stack.pop()] = a[i]; //스택에 입력된 index의 배열값에 현재 배열값을 덮어씌워준다.
			}
			stack.push(i); // 스택에 현재 index 값을 넣어준다.
		}
		
		while (!stack.isEmpty()) {
			a[stack.pop()] = -1; // 스택에 남은 값들은 오큰수가 없어 -1을 대입
		}
		
		for (int i : a) {
			sb.append(i + " "); // 값을 StringBuilder에 담아준다.
		}
		
		System.out.println(sb); // 정답을 출력.
	}

}