[BOJ 17298] 오큰수 (java)

문제 링크 https://www.acmicpc.net/problem/17298

이중for문으로 다 푼줄 알았는데 제출했더니 시간초과가 났다 ㅠ 그래서 백준 참고해서 풀었더니 무난히 통과

문제

/* 시간 초과때문에 통과 x인 코드
	 * BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		Stack<Integer> stack = new Stack<Integer>();
		int n = Integer.parseInt(br.readLine());
		Integer[] array = new Integer[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i =0;i<n;i++) {
			array[i]=Integer.parseInt(st.nextToken());
		}
		
		for (int i = 0; i < n; i++) {
			stack.clear();
			for (int j = n - 1; j != i; j--) {
				if (array[i] < array[j]) {
					stack.push(array[j]);
				}
			}
			if (!stack.isEmpty()) {
				bw.write(stack.pop()+" ");
			}else {
				bw.write(-1+" ");
			}
		}
		
		bw.flush();
		bw.close();

	}*/

문제 풀이

package basics_200;

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 BOJ17298 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		Stack<Integer> stack = new Stack<Integer>();
		int n = Integer.parseInt(br.readLine());
		Integer[] array = new Integer[n];
		Integer[] result = new Integer[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}

		stack.push(0);
		for (int j = 1; j < n; j++) {
			// 바로옆의 수가 오큰수라면
			// 해당 인덱스(스택 맨위)에 오큰수를 넣어주고, 오큰수를 찾았으니까 스택에서 pop
			// ! 스택에 인덱스를 저장해두는거니까 오큰수를 꼭 차례대로 찾아야한다는 생각을 버리기 !
			while (!stack.isEmpty() && array[stack.peek()] < array[j]) {
				result[stack.peek()] = array[j];
				stack.pop();
			}
			stack.push(j);
		}
		
		//for문을 다 돌고나면 스택에 가장 마지막 수가 있음 
		while(!stack.isEmpty()) {
			result[stack.peek()]=-1;
			stack.pop();
		}
		
		for(int number:result) {
			bw.write(number+" ");
		}

		bw.flush();
		bw.close();

	}