<Algorithm> 168. 큰수만들기(Programmers)

1. 큰수만들기(Programmers)

   사용 알고리즘 :  그리디

• 오랜만에 그리디 문제를 풀었는데 확실히 그리디는 규칙을 찾아내는것이 필요한것 같다.

• char 배열은 new String(char)로 문자열로 변경이 가능하다.

문제에 대한 접근&생각

1. 문자열을 탐색하면서 각 순서마다 큰수를 구해야함 -> 그리디

다른 방법 풀이

• Stack을 이용해 크기비교를 통해서 가장 큰수가 되는 문자열을 쌓는다.

내 코드 

class Solution {
    public static void main(String[] args) {
        System.out.println(solution("784542123132813531535156541313", 2));
    }
    public static String solution(String number, int k) {
        int resLen = number.length() - k;
        /******************************
         * 문자열을 탐색하면서 가장 큰 수를 판단하는
         * 그리디를 이용하여 답을 출력한다.
         *******************************/
        if(number.charAt(0) == '0') return "0";
        char[] nums = number.toCharArray();
        int start_idx = 0;
        StringBuilder sb = new StringBuilder();
        while (resLen > 0) {
            int max = -1;
            int max_idx = 0;
            for(int i = start_idx; i <= nums.length-resLen; i++){
                if(max < nums[i]-'0') {
                    max = nums[i]-'0';
                    max_idx = i;
                }
            }
            start_idx = max_idx+1;
            sb.append(max);
            resLen--;
        }
        
        return sb.toString();
    }
}