[백준/Java] 17298 오큰수

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

17298번: 오큰수

 

입력조건이 1000000까지인 걸로 보아 2중 for문으로 접근하면 시간 초과가 날 것으로 예상할 수 있고, 스택으로 접근하였습니다.

수열을 탐색하면서 현재 원소가 이전의 원소보다 작을 때 까지 수열의 index를 스택에 push 하고,

현재 원소가 수열[스택의 top 원소값]보다 크게 될 경우 stack의 원소를 pop하면서 해당 인덱스에 해당하는 원소들을 현재 원소로 바꿔주면 됩니다.

또한 스택의 원소를 다루는 pop()이나 peek()에서 스택이 비어있다면 예외에러가 발생하기 때문에, 조건을 제시할 때 isempty()의 연산 순서를 고려하는 것도 필요합니다. 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Stack;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Stack<Integer> stack = new Stack<Integer>();
		
		int N = Integer.parseInt(br.readLine());
		int[] seq = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(int i = 0; i < N; i++) {
			seq[i] = Integer.parseInt(st.nextToken());
		}
		for(int i = 0; i < N; i++) {
			while(!stack.isEmpty() && seq[stack.peek()] < seq[i]) {
				seq[stack.pop()] = seq[i];
			}
			stack.push(i);
		}
		while(!stack.isEmpty()) {
			seq[stack.pop()] = -1;
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < N; i++) {
			sb.append(seq[i]).append(' ');
		}
		
		System.out.println(sb);
	}
}