백준 17298 오큰수

백준문제링크

수가 크기에 정렬은 사용할수 없다.스택을 이용해서 문제를 풀어주자

import java.util.*;
import java.io.*;
import java.time.*;


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));
    int N = Integer.parseInt(br.readLine());
    // 입력한 숫자 배열
    int[] arr =new int[N];
    // 오큰수 저장 배열
    int[] ans = new int[N];
    StringTokenizer st = new StringTokenizer(br.readLine()," ");
    //사용자가 입력한 배열 저장하고
    for(int i=0;i<N;i++){
      arr[i]=Integer.parseInt(st.nextToken());
    }
    Stack<Integer> stack = new Stack<>();
	// 스택이 비어있으니 일단 0으로 초기화해준다.
    stack.push(0);
    // 스택에는 인덱스를 넣고 입력 배열과 정답 배열을 비교한다.
    // 정답 배열에 답을 업데이트 할 때 그 수의 인덱스를 알아야 한다.그렇기에 값 대신 수열의 인덱스를 스택에 저장한다.값은 배열에 인덱스 넣으면 어차피 알수 있다.
    for(int i=1;i<N;i++){
    // !stack.isEmpty 반드시 넣어야 함!!안 그러면 비어있는 스택에 pop을 시도하게 됨
      while(!stack.isEmpty() && arr[stack.peek()]<arr[i]){
        // arr[i]가 크면 계속 pop한다.
        ans[stack.pop()] = arr[i];
      }
      stack.push(i);
    }
	// 스택이 비어있지 않다 = 오큰수가 존재하지 않는 숫자들만 스택에 남아있다 = 전부 -1로 바꿔주자
    if(!stack.isEmpty()){
      while(!stack.isEmpty()){
        ans[stack.pop()]=-1;
      }
    }
    for(int i=0;i<N;i++){
      bw.write(ans[i]+" ");
    }
    bw.flush();
    bw.close();
    br.close();
  }
}