[Java]BOJ17298_오큰수

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

17298번: 오큰수

---

수열 A의 크기가 백만이므로 N²으로는 시간초과가 난다. 따라서 O(N)으로 해결할 방법을 생각해야한다.

 

자신을 기준으로 오른쪽 수를 봐야할 경우 보통 뒤에서 시작하는 것이 좋을 때가 많다.

 

이 문제의 핵심은 오른쪽에서 자신보다 큰 수만 남겨놓는 것이다. 만약 9 5 2 7 순으로 수열이 있다면 5라는 숫자를 볼 때 2와 7을 보는데 7은 남기고 2는 버리는 것이다. 왜냐하면 5 다음의 9를 볼 때를 생각해보면 된다.

9는 자신보다 큰 수를 오른쪽에서 찾는데 5를 보고 다음 2를 봐야하지만 2는 5를 볼 때 이미 5보다 작다는 것을 확인했으므로 미리 지워놓는 것이다.

 

따라서 스택을 이용하여 뒤에서부터 확인하는 작업을 했다. 맨 마지막 수는 오른쪽에 수가 없으므로 항상 -1이다.

 

1번 예시로 설명하자면, 7을 처음에 스택에 담는다. res = {-1, -1, -1, -1}, stack = [7]

2를 7과 비교하고 7이 크므로 res배열에 7을 담는다. 그리고 2를 스택에 담는다. res = {-1, -1, 7, -1}, stack =[7, 2]

5와 2를 비교하면 2가 작으므로 2를 스택에서 뺀다. 그 후 7과 비교하여 7이 더 크므로 res배열에 7을 담고 5를 스택에 담는다. res = {-1, 7, 7, -1}, stack = [7, 5]

3과 5를 비교하면 5가 크므로 res배열에 5를 담고 3을 스택에 담는다. res = {5, 7, 7, -1}, stack = [7, 5, 3]

 

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] res = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			res[i] = -1;
		}
		Stack<Integer> stack = new Stack<>();
		stack.push(arr[N-1]);
		for (int i = N-2; i >= 0; i--) {
			while(!stack.isEmpty()) {
				if(arr[i] >= stack.peek()) stack.pop();
				else {
					res[i] = stack.peek();
					break;
				}
			}
			stack.push(arr[i]);
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < N; i++) {
			sb.append(res[i]).append(" ");
		}
		System.out.println(sb);
	}

}