BOJ_17298 : 오큰수

👉 문제링크

17298번: 오큰수

---

---

🔸 문제 분석 🔸

• 배열arr을 입력받으면, 한 인덱스 i의 오른쪽으로 처음 등장하는 arr[i] 보다 큰 값(오큰수)을 정답 배열 answer[i]에 저장한다.
• n이 1,000,000(백만)이므로 인덱스마다 오른쪽 탐색을 진행하면 O(n^2)로 시간초과가 난다.
• 스택을 이용해서 오큰수를 찾지 못한 인덱스만 스택에 남기며 계산을 진행한다.
  • 스택의 arr[top]이 push하려는 arr[i]보다 작다면, 인덱스 top의 오큰수는 arr[i]이다.
  • 배열 순회가 끝나도 스택에 남아있는 인덱스의 값들은 오큰수가 없으므로 -1로 출력한다.

🔸 코드 🔸

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));
        StringBuilder sb = new StringBuilder();

        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<>();

        for (int i = 0; i < n; i++) {
            while (!stack.empty() && arr[stack.peek()] < arr[i]){
                answer[stack.pop()] = arr[i];
            }
            stack.push(i);
        }

        for (int i : answer){
            if (i == 0)
                sb.append("-1 ");
            else
                sb.append(i + " ");
        }
        System.out.println(sb.toString());
    }
}

🔸 코드 해석 🔸

• 배열의 수 n과 배열 arr를 입력받는다. 정답을 저장할 배열 answer도 선언한다.
• 배열 arr를 순회하며 arr[top]과 arr[i]를 비교해 스택에 넣고 빼며 배열 answer를 채운다.
  • arr[top] < arr[i] 이면, answer[top] = arr[i]

---

🔸 end 🔸

• 처음엔 새로운 스택 활용법이라 생각해서 이해하기 어려웠는데, 막상 이해하고보니 간단한 원리인 것 같다.