[백준 17928] 오큰수 / 자바 / 스택

문제         

레벨: G4
알고리즘: 스택 
풀이시간: 3:41
힌트 참조 유무:

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

1 번째 시도   

이 문제는 이중 for문으로 하면 쉽게 풀 수 있지만 1,000,000 x  1,000,000이니 반드시 시간초과가 난다.


 스택이 비어있지 않으면서 현재 원소가 스택의 맨 위 원소가 가리키는 원소보다 큰 경우
 해당 조건을 만족할 때 까지 stack의 원소를 pop하면서
 해당 인덱스의 값을 현재 원소로 바꿔준다.  

배열을 다 순회했다면
  스택의 모든 원소를 pop하면서 해당 인덱스의 value를
  -1로 초기화한다.

 

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);
	}
}