[17298] 오큰수

🔗 문제 링크

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

❔ 문제 설명

크기가 N인 수열 $A = A_1, A_2, ..., A_N$이 있다. 수열의 각 원소 $A_i$에 대해서 오큰수 NGE(i)를 구하려고 한다. $A_i$의 오큰수는 오른쪽에 있으면서 $A_i$보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

⚠️ 제한사항

• 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

• 둘째에 수열 A의 원소 $A_1, A_2, ..., A_N (1 ≤ A_i ≤ 1,000,000)$이 주어진다.

---

💡 풀이 (언어 : Java)

풀이에 실패해 타인의 아이디어를 공부했다. 나는 처음에 큐를 사용할 생각을 했다가 스택도 생각해봤는데, 여기 위치를 어떻게 보존해주면서 값을 비교하지? 이런 생각을 했는데, 인덱스를 스택에 넣어주고 꺼내서 배열의 원소를 참조해서 비교하면 됐다. 많이 배운 문제이다.

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

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 배열로 변환
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            // 스택에 넣은 위치 인덱스가 존재하면 그걸로 값을 가져와 현재 원소와 비교한다
            // 만약 현재 원소가 더 크면 스택의 원소를 제거하면서 배열의 해당 위치 값을 현재 원소로 바꾼다
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                arr[stack.pop()] = arr[i];
            }
            // 현재 원소가 더 작거나, 스택에 비교할 수가 없으면 현재의 원소를 넣는다
            stack.push(i);
        }
        // 스택에 남아 있는 인덱스는 오큰수가 없는 것들이므로 스택에서 모두 뽑아서 해당 배열 값을 -1로 바꿈
        while (!stack.isEmpty()) {
            arr[stack.pop()] = -1;
        }
        StringBuilder sb = new StringBuilder();
        for (int num : arr) {
            sb.append(num).append(" ");
        }
        System.out.print(sb);
    }
}