[백준 17298] 오큰수 - 자바

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

17298번: 오큰수

---

1. 풀이

문제의 이해부터 하고자 한다.

Ai의 오큰수 : 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

처음 문제를 보자마자 반복문만으로 하려고 했으나, 2중 반복문을 사용할 경우 제곱의 시간 복잡도가 나오는데

수열의 입력 값이 1,000,000이기 때문에 1초 ( 대략 1억 )를 넘어가기 때문에 '시간초과'가 발생한다.

 

삽질을 계속하다, 백준의 강의를 통해 다시 한번 풀이를 알 수 있었다. ( 돈이 최고 )

결국 찾아낸 방법은 스택에 아직 오큰수를 구하지 않은 수의 인덱스를 넣는 방법을 사용한다.

스택을 활용한 문제들은 인덱스를 넣어서 구하는 경우가 많은 것 같다

다시 한번 풀어볼 필요가 있는 문제이다.

 

---

2. 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(bf.readLine());
		Stack<Integer> stack = new Stack<Integer>();
		int[] nums = new int[num];
		int[] result = new int[num];
		String[] input = bf.readLine().split(" ");
		for(int i = 0; i < num; i++)
			nums[i] = Integer.parseInt(input[i]);
		
		stack.push(0);
		for(int i = 1; i < num; i++) {
			while(!stack.isEmpty() && nums[stack.peek()] < nums[i])
				result[stack.pop()] = nums[i];
			stack.push(i);
		}
		
		while(!stack.isEmpty())
			result[stack.pop()] = -1;
		
		BufferedWriter bw = new BufferedWriter(new 	OutputStreamWriter(System.out));
		
		for(int i = 0; i < num; i++)
			bw.write(result[i]+" ");
		
		bw.flush();
		return;
	}
}