[JAVA]17299 오등큰수(골드3, 스택)

 📚 문제  

17299번: 오등큰수

🔍 아이디어  

해당 문제는 문제를 이해하는데 시간이 조금 걸렸습니다.

간추려서 말하면 각 숫자의 개수를 세고 i 번째 숫자의 오른쪽에 arr내의 i가 있는 숫자보다 더 많은 숫자를 가지고 있는 숫자를 출력하면 됩니다.  

 

arr : 입력 숫자 배열

dp(numCnt) : 각 숫자의 개수

stack<int[]> -> int[3] = {인덱스, 해당 인덱스의 숫자, arr 내의 해당 숫자의 개수) //아래 풀이에서는 [2]번째 것을 생략했습니다.

ans : 결과

스택에 들어오는 값의 개수가 stack의 peek의 개수보다 크면 해당 인덱스에 현재 값을 입력합니다.

위의 그림에서는 스택은 쌓이는 순서로 봐주시면 감사하겠습니다. 

📝 풀이 

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

public class boj_17299_오등큰수2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

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

        int[] arr = new int[size + 1];
        int[] numCnt = new int[1_000_001];
        
        //숫자의 개수를 센다 (기수 정렬과 같아 bucket에 담는 방법)
        for (int i = 1; i <= size; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            numCnt[arr[i]]++;
        }

        Stack<int[]> stack = new Stack<>();
        int[] ans = new int[size + 1];
        for (int i = 1; i <= size; i++) {
            int[] temp = new int[]{i, arr[i]}; //인덱스, 해당 숫자
            while (!stack.isEmpty() && numCnt[stack.peek()[1]] < numCnt[temp[1]]) { 
                //개수가 더 많은 숫자가 들어오면 해당 값에 따라 앞의 인데스를 채워준다.
                int[] pop = stack.pop();
                ans[pop[0]] = temp[1]; //ans[가능 idx] = arr[i]
            }
            stack.push(temp);
        }

        for (int i = 1; i <= size; i++) {
            sb.append(ans[i] == 0 ? -1 : ans[i]).append(" "); //채워지지 않은 경우 -1
        }
        System.out.println(sb);
    }
}

해당 풀이는 996ms를 소요했고 

 

하단의 풀이는 992ms를 소요했습니다.

차이점은 stack에 인덱스, 숫자, 숫자의 개수를 모두 넣어 쉽게 쉽게 비교하였습니다. (메모리 사용량은 더 높은것을 확인할 수 있습니다.)

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

public class boj_17299_오등큰수 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

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

        int[] arr = new int[size + 1];
        int[] dp = new int[1_000_001];
        for (int i = 1; i <= size; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            dp[arr[i]]++;
        }

        Stack<int[]> stack = new Stack<>();
        int[] ans = new int[size + 1];
        for (int i = 1; i <= size; i++) {
            int[] temp = new int[]{i, arr[i], dp[arr[i]]}; //인덱스, 숫자, 숫자의 개수
            while (!stack.isEmpty() && stack.peek()[2] < temp[2]) {
                int[] pop = stack.pop();
                ans[pop[0]] = temp[1]; //ans[가능 idx] = arr[i]
            }
            stack.push(temp);
        }

        for (int i = 1; i <= size; i++) {
            sb.append(ans[i] == 0 ? -1 : ans[i]).append(" ");
        }
        System.out.println(sb);

    }
}