[프로그래머스] LV2 큰 수 만들기

 

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

코딩테스트 연습 - 큰 수 만들기

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

 

★풀이 방법★

이 문제는 주어진 숫자중에서 큰 수를 k개 만큼 숫자를 뺀 다음, 가장 큰 수를 만드는 문제인데 문제를 읽기전에는 그냥 거꾸로 정렬해서 큰 수부터 차례대로 출력하면 되는줄 알았다. 만약 그랬다면 LV2가 아니라 LV1에 있었을 것이다.

 

이 문제의 핵심은 '자리수'를 무시할 수 없다는 것이다.

만약 number가 "4177252841" 이고, K가 4라면 총 구해야하는 자리수는 6자리이다.

6자리의 숫자를 구해야하기 때문에 첫번쨰 자리에 올 숫자는 아래 그림과 같이 무조건 index 4 이하에서 구해야한다.

만약 첫번쨰 자리 숫자를 구할때 4 1 7 7 2 5 2 8 4 1에서   5를 고르게 된다면, 6의자리 숫자를 만들 수 없게된다.

 

여기서 최소로 요구되는 자리수를 구할때,

int size = number.length() - k; //구해야하는 자리수
int demand = number.length() - size; // 즉 , K와 같다.

마지막으로 최댓값을 갱신할 때마다 다음 탐색은 최댓값 다음 인덱스부터 진행해야 하기 때문에 인덱스를 갱신해 준다.

 

 

추가로 숫자중에 가장 큰 수인 9가 나오게된다면 더이상 최대값을 갱신할 필요가 없다.

 

public class 큰수만들기 {
    public static String solution(String number, int k) {

        int size = number.length()-k; //구해야하는 자리수
        int max =  Integer.MIN_VALUE;
        int index = 0;
        int j;
        StringBuilder builder = new StringBuilder();
        for(int i=0; i<size; i++){
            for( j = index; j<=k; j++) {
                int num = number.charAt(j) -'0';

                if(num == 9) {
                    max = num;
                    index= j+1;

                    break;
                }

                if(max < num) {
                    max = num;
                    index= j+1;

                }
            }

            builder.append(max);
            max = Integer.MIN_VALUE;
            k++;


        }

        return builder.toString();
    }