큰 수 만들기 (탐욕법(Greedy))

원본 : https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

 

풀이

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        int[] arr = Arrays.stream(number.split("")).mapToInt(Integer::parseInt).toArray();
        int[] answer = new int[arr.length];
        Arrays.fill(answer, -1);

        int cnt = 1;
        Stack<int[]> stack = new Stack<>();
        int maxIdx = getMaxIdx(arr, 0, arr.length - 1);

        answer[maxIdx] = arr[maxIdx];
        stack.add(new int[]{0, maxIdx - 1});
        stack.add(new int[]{maxIdx + 1, arr.length - 1});

        if (cnt == arr.length - k) {
            return getAnswer(answer);
        }

        while (!stack.isEmpty()) {
            int[] temp = stack.pop();
            int startIdx = temp[0];
            int endIdx = temp[1];

            if (startIdx <= endIdx) {
                maxIdx = getMaxIdx(arr, startIdx, endIdx);
                cnt++;
                answer[maxIdx] = arr[maxIdx];
                stack.add(new int[]{startIdx, maxIdx - 1});
                stack.add(new int[]{maxIdx + 1, endIdx});
            }

            if (cnt == arr.length - k) {
                return getAnswer(answer);
            }
        }

        return "";
    }

    public int getMaxIdx(int[] arr, int startIdx, int endIdx) {
        int max = -1;
        int maxIdx = -1;

        for (int i = startIdx; i <= endIdx; i++) {
            if (arr[i] > max) {
                max = arr[i];
                maxIdx = i;
            }
        }

        return maxIdx;
    }

    public String getAnswer(int[] arr) {
        StringBuilder sb = new StringBuilder();

        for (int num : arr) {
            if (num != -1) {
                sb.append(num);
            }
        }

        return sb.toString();
    }
}