10주차. 오큰수

17298. 오큰수

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

17298번: 오큰수

📌문제

- 예제1

  📝입력

4
3 5 2 7

  💻출력

5 7 7 -1

📌풀이

992ms 147952kb

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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];
        int[] answer = new int[n];

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

        stack.add(0);
        for(int i = 1; i < n; i++){
            while( !stack.isEmpty() && arr[stack.peek()] < arr[i]){
                answer[stack.pop()] = arr[i];
            }
            stack.add(i);
        }
        StringBuilder sb = new StringBuilder();
        for(int num : answer){
            if(num == 0) num = -1;
            sb.append(num).append(" ");
        }
        System.out.print(sb);
    }

}

스택에 인덱스를 넣어주고 스택 top 값이 현재 비교하려는 배열의 값보다 작다면 오큰수에 해당하니 정답 배열에 해당 값을 넣어준다. 이런 식으로 하다보면 정답 배열 값에 0인 인덱스들이 있는데 이것들은 오큰수가 없는 경우이므로 -1로 출력해준다. 

 

stack에 index를 넣어주고 변곡점을 찾아서 stack에 들어있는 값과 비교하는 이 풀이 방법을 알고 있다면 어렵지 않은 문제다. 그동안 주구장창 stack 문제를 풀었던 나날들이 헛되지 않았구나.. 싶었다.