Programmers 큰 수 만들기 java 풀이

문제 설명

어떤 숫자에서 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 +1) 이기 때문에 그 중 가장 큰 숫자를 고른다. 만약 가장 큰 수와 같은 수가 있다면 젤 앞쪽에 오는 수를 선택한다. 그리고 다시 다음자리에 올 수 있는 범위를 정하고, 그중에 가장 큰 수를 고르길 반복한다. 포인트는 매번 젤 큰수를 선택할때 범위를 지정하는 것인데, 예를 들어 남은 숫자가 5자리이고 5개의 숫자를 골라야 한다면 매번 고를 숫자는 한 가지로 고정 될 것이다. 이번 문제는 말 그래도 그리디(탐욕법) 알고리즘이 무엇인지 느낌이 확 와닿는 문제였다.

 

코드

import  java.util.*;
class Solution {
    public String solution(String number, int k) {
        String answer;
        
        int length = number.length();
        int count = length - k;
        int left = 0;
        int right = length - count;
        int idx=0, max, temp;
        
        StringBuilder sb = new StringBuilder();
        while(count>0) {
            max = -1;
            for(int i = left; i<=right; i++) {
                temp = number.charAt(i) - '0';
                if(temp>max) {
                    max = temp;
                    idx = i;
                }
            }
            sb.append(number.charAt(idx));
            count--;
            left = idx+1;
            right = length - count;
        }
        
        
        return answer = sb.toString();
    }
}