[백준 17298번] 오큰수

문제 링크: 17298번 오큰수

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

 

프로그래머스 레벨 2였나... 주식 가격 문제와 비슷하다.

수열의 원소들을 쭉 받아주면서, 해당 숫자의 인덱스와 함께 묶어 스택에 push한다.

그리고 스택의 top에 있는 숫자보다 새로 받은 숫자가 더 크면, 더 작은 숫자가 나올때까지 스택을 pop해나가면서 각 인덱스에 새로 받은 숫자를 채워준다.

이런 과정을 반복했을 때 남은 숫자는 자신보다 더 큰 숫자를 만나지 못한 숫자들이므로, 스택에 남아있는 모든 아이템을 확인하면서 해당 인덱스의 자리에 -1을 채워준다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
​​​​static class NumAndIdx {
​​​​​​​​int num;
​​​​​​​​int idx;

​​​​​​​​NumAndIdx (int num, int idx) {
​​​​​​​​​​​​this.num = num;
​​​​​​​​​​​​this.idx = idx;
​​​​​​​​}
​​​​}

​​​​public static void main(String[] args) throws IOException {
​​​​​​​​BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
​​​​​​​​StringTokenizer st;

​​​​​​​​st = new StringTokenizer(br.readLine());
​​​​​​​​int n = Integer.parseInt(st.nextToken());
​​​​​​​​int[] answer = new int[n];

​​​​​​​​Stack<NumAndIdx> stack = new Stack<>();

​​​​​​​​st = new StringTokenizer(br.readLine());
​​​​​​​​for (int idx = 0; idx < n; idx++) {
​​​​​​​​​​​​int cur = Integer.parseInt(st.nextToken());

​​​​​​​​​​​​while (!stack.isEmpty() && cur > stack.peek().num) {
​​​​​​​​​​​​​​​​NumAndIdx top = stack.pop();
​​​​​​​​​​​​​​​​answer[top.idx] = cur;
​​​​​​​​​​​​}

​​​​​​​​​​​​stack.push(new NumAndIdx(cur, idx));
​​​​​​​​}

​​​​​​​​while (!stack.empty())
​​​​​​​​​​​​answer[stack.pop().idx] = -1;

​​​​​​​​StringBuilder sb = new StringBuilder();
​​​​​​​​for (int item : answer)
​​​​​​​​​​​​sb.append(item).append(' ');
​​​​​​​​System.out.print(sb);
​​​​}
}