프로그래머스 큰 수 만들기

그리디 알고리즘을 이용하여 푸는 문제

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

프로그래머스

 

처음에 어떤식으로 풀어야할 지 전혀 감이 잡히지 않았지만 n-k 자리의 정수중 최대값을 만드는 것이라는 걸 깨닫고 n-k자리가 될 수 있는 수 중 최대값을 넣고 그 다음은 n-k-1,n-k-2........ 1  의 자리가 될 수 있는 수들 중 최대값을 구하는 방식으로 문제를 해결했다. 문제를 제출할때 하나의 케이스에서 시간초과가 발생했는데 StringBuilder를 사용하지않고 String을 사용해서 생긴 문제였다. 확실히 StringBuilder를 사용하면 속도가 훨씬 빠르긴한 것 같다.

 

 

풀이코드

 public static String solution(String number,int k) {
        StringBuilder sb = new StringBuilder();
        int len = number.length();
        int[]num = new int[len];
        for(int i=0;i<len;i++)
        {
            num[i] = Integer.parseInt(number.substring(i,i+1));
        }
        int i = 0,j=0;
        int make = len-k;
        while(i<len) {
            int max = -1;
            int maxIndex =-1;
            for (; i <= len - make + j; i++) {
                if (max < num[i]) {
                    max = num[i];
                    maxIndex = i;
                }
            }
            sb.append(max);
 
            num[maxIndex] = -1;
            i = maxIndex+1;
            j++;
            if(sb.length()==make)break;
        }
 
        return sb.toString();
    }