[백준] 🥇 17298 오큰수

📌 난이도

🥇 Gold 4

📌 문제

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

📌 풀이

이 문제를 보자마자든 생각은 바로 DP를 응용하여 풀어야겠다는 생각이였다.
일반적으로 오른쪽에서 왼쪽로 가면서 이전에 가장 큰값이 있는지 비교를 하려면 o(n^2/2)의 시간복잡도가 발생하므로, 너무나도 긴 시간이 걸리게 된다.
하지만 그렇다고 이전에 가장 큰 값이 어떤건지만 저장을 해놓으면, 최적해가 나오지를 않는다.

이를 해결하기 위하여 주소값을 저장하는 dp 배열을 만들어서, 그 안에는 그것보다 큰 오른쪽에 있는 숫자의 주소값이 들어가게 하였다.

📌 Code

package BOJ.DS;

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

public class N17298 {
    static int[] nums;
    static int[] dp;

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

        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        nums = new int[N];
        dp = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        FindNGE(N);
        ShowAll(N);
    }

    static void FindNGE(int N) {
        dp[N - 1] = -1;
        for (int i = N - 2; i >= 0; i--) {
            // 주소값
            dp[i] = i + 1;
            // 주소값이 -1이 아니고, 더 크면
            while (nums[i] >= nums[dp[i]]) {
                if (dp[dp[i]] != -1) {
                    dp[i] = dp[dp[i]];
                } else{
                    dp[i] = -1;
                    break;
                }
            }
        }
    }

    static void ShowAll(int N) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            if (dp[i] != -1) {
                sb.append(nums[dp[i]] + " ");
            } else {
                sb.append(-1 +" ");
            }
        }
        System.out.println(sb);
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁