탐욕법 - 큰 수 만들기

이 문제는 주어진 숫자 문자열에서 k개의 숫자를 제거하여 만들 수 있는 가장 큰 숫자를 찾는 문제이다. 문제를 해결하기 위해서 각 숫자를 왼쪽에서부터 하나씩 선택하면서 최종적으로 가장 큰 숫자를 만들 수 있는 방법을 찾아야 한다.

import java.util.*;

class Solution {
    public String solution(String number, int k) {        
        
        int len = number.length() - k - 1;
        int idx = 0;
        
        StringBuilder sb = new StringBuilder();
        
        while(len >= 0){
            char max = '0';
            for(int i = idx; i < number.length() - len; i++){
                if(number.charAt(i) > max){
                    max = number.charAt(i);
                    idx = i + 1;
                    if(number.charAt(i) == '9'){
                        break;
                    }
                }    
            }
            sb.append(max);
            len--;
        }  
        
        return sb.toString();
    }      
}

 

문제분석

 - 초기 설정에 len = number.length() - k - 1 : 만들어야 하는 숫자의 길이를 계산해준다.

 - idx  = 0 으로 현재 탐색할 시작 인덱스를 저장해준다.

 - StringBuilder sb = new StringBuilder(); 최종 결과를 저장할 StringBuilder 를 만들어준다.

 

while 로 루프는 만들고자 하는 숫자의 길이만큼 반복하고 max = 9 초기 최대값을 0으로 해준다.

선택된 최대값이 9라면 더 이상 큰 숫자가 없으므로 루플에서 빠져나가고 선택된 최대 숫자는 sb에 추가해준다.

 

 

 

 

총 정리

---

한 번 탐색 시 한 자릿수의 최대값을 찾아야한다. 만약 최대값이 9 가 오면 sb에 저장하고 반복문을 게속 돌면서 9 가 더이상 없으면 그 다음 큰 숫자를 찾아서 저장하는 방식이다. 숫자의 길이가 얼마나 있냐에 따라 시간 복잡도가 달라진다. 지금코드로 봤을때는 O(n * k) 이다. n는 number 문자열의 길이고, k는 제거할 숫자의 개수이다.