BOJ 17289 오큰수 by Java

ejjem·2025년 8월 14일

목록 보기

16/20

문제 풀이 날짜: 2025-08-14

💡Github URL

https://github.com/ejjem/coding-test/tree/main/%EB%B0%B1%EC%A4%80/Gold/17298.%E2%80%85%EC%98%A4%ED%81%B0%EC%88%98

💡 초기 접근

최댓값을 매번 갱신하지 않고 찾아야 한다고 생각해 직전 글에서 공부한 단조 덱을 사용해보려고 했음. 그러나 문제의 조건이 달라 사용할 수 없는 상황이었음.
이 문제에서는 내 오른쪽 모든 값들 중 최댓값이 아닌, 내 오른쪽 값들 중 '가장 빨리 나오는(index가 가장 작은, 조건에 맞는 것들 중 가장 왼쪽 등등) 나보다 큰 수'를 찾는 것이기 때문. 이번에도 숫자가 매우 크기 때문에 매번 탐색을 하면서 조건에 만족하는 수를 찾으면 시간 초과가 발생하기 때문에, 새로운 알고리즘이 필요하다고 느낌.
때문에 이번에는 단조 스택을 사용할 예정.

💡알고리즘 설계

stack을 하나 생성. stack에다가는 index만 넣을 예정.
stack에서 나올 때 정답값을 갱신하는 구조를 이용할 것임.

반복문을 돌리면서 아래 조건문을 진행. (i는 1 ~ N)

value[top] > value[i]
stack에 i를 push.
push(i)
value[top] <= value[i]
stack이 비거나, 다시 1번 조건 value[top] > value[i]를 만족할 때 까지 pop.
pop()
이 때, pop되어 나온 index들의 '오큰수'는 value[i]인 것이기 때문에 정답값으로 갱신.

이를 i = N 까지 시행한 다음에도 stack에 남아 있는 index들은 '오큰수'가 없는 값들이기 때문에 전부 pop() 하면서 -1을 정답값으로 갱신.
++ 처음부터 그냥 정답값을 저장할 배열을 -1로 초기화한 다음에, '오큰수'를 찾은 index만 갱신하는게 더 좋을 거 같아 수정.

stack을 이용해, 본인 이후의 index들 중에서 본인보다 큰 value를 가진 것이 나올 때 까지 stack에 계속 저장한다. 그러다가 조건에 만족하는 value를 가진 값이 나온다면, stack 내부의 모든 index들의 오큰수가 나타난 것이기 때문에 갱신하는 풀이 과정.

이 방식을 사용하면 O(N)으로 순회를 1번만 하면서도 문제를 해결할 수 있음.

💡코드

메모리: 152172 KB, 시간: 792 ms

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static StringBuilder sb;
	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		ArrayDeque<Integer> stack = new ArrayDeque<>();
		int[] number = new int[N];
		int[] answer = new int[N];
		sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			number[i] = Integer.parseInt(st.nextToken());
			answer[i] = -1;
		}
		stack.offerLast(0);
		for(int i=1; i<N; i++) {
			while(!(stack.isEmpty()) && number[i] > number[stack.peekLast()] ) {
				answer[stack.pollLast()] = number[i];
			}
			stack.offerLast(i);
		}
		for(int i=0; i<N; i++) {
			sb.append(answer[i]).append(" ");
		}
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

💡시간복잡도

O(N)

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static StringBuilder sb;
	static class Node{
		int idx, val;
		Node(int idx, int val){
			this.idx = idx;
			this.val = val;
		}
	}
	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		ArrayDeque<Node> deque = new ArrayDeque<>();
		st = new StringTokenizer(br.readLine());
		deque.offerLast(new Node(0, Integer.parseInt(st.nextToken())));
		for(int i=1; i<N; i++) {
			Node last = deque.peekLast();
			int last_val = last.val;
			int tmp = Integer.parseInt(st.nextToken());
			if(last_val > tmp) continue;
			else {
				//if(last_val < tmp) deque.pollLast();
				deque.offerLast(new Node(i, tmp));
			}
		}
		sb = new StringBuilder();
		for(int i=0; i<N; i++) {
			while(true) {
				if(deque.isEmpty()) break;
				Node first = deque.peekFirst();
				if(first.idx <= i) deque.pollFirst();
				else break;
			}
			if(deque.isEmpty()) sb.append(-1).append(" ");
			else {
				Node maximum = deque.peekFirst();
				sb.append(maximum.val).append(" ");
			}
		}
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		
	}
}