프로그래머스 - 탐욕법 ( Greedy ) - 큰 수 만들기

---

 

---

[ 코드 보기 ]

 

import java.util.*;

class Solution {
    
    public String solution(String number, int k) {
        
        // ==================================================================
        // + 문제 접근을 가장 작은 숫자 k개를 삭제하는 것이 아니라
        // + 가장 큰 숫자 number.length() - k개를 구하여 붙이는 식으로 수행하였다.
        // ==================================================================
        
        StringBuilder sb = new StringBuilder();
        // + 최종적으로 String의 형태를 지녀야하기에, StringBuilder를 활용한다.
        
        // 1. 가장 큰 값의 인덱스 정보
        int idx = 0;
        
        // 2. 만들어야 하는 자리의 수
        int size = number.length() - k;
        
        // 3. 각 자리를 반복하는 for 반복문
        // + 최대값을 만들기 위해서 반복문을 통해 첫번째 자리부터 하나씩 만들어 간다.
        for ( int i = 1; i <= size; i++ ) {
            
            // 4. 최대값을 저장하는 변수
            int max = Integer.MIN_VALUE;
            
            // 5. 만들어야 하는 수(최대값)의 각 자리의 수를 정하기 위해 정해진 범위를 탐색하는 반복문
            // + 받은 문자열의 길이 - ( 만들어야 하는 자리수 - 현재 만들고 있는 자리수 )
            // + 그 이유는 만들어야 하는 자리수 - 현재 만들고 있는 자리수를 하면 이미 만들어진 자리수가 나오기에
            // + 받은 문자열 길이 - 이미 만들어진 자리수를 통해서 이미 완성된 부분을 빼고 그 외의 자릿수부터 구하게 된다.
            for ( int j = 0; j < ( number.length() - ( size - i ) ); j++ ) {
            
                // 6. 해당 위치의 숫자가 9일 경우에는 바로 최대 숫자를 갱신해 준다.
                // + 9일 경우에는 어느 수가 와도 9가 크기에 반복문에서 바로 벗어나 준다.
                if ( (number.charAt(j) - '0') == 9 ) {
                    
                    max = 9;
                    idx = j;
                    break;
                    
                } // inner if
                
                // 7. 그 외의 경우의 최댓값을 구한다.
                // + 그 외의 경우에는 반복문을 통해서 비교를 통해 하나씩 최대값을 얻어와 준다.
                if ( max < (number.charAt(j) - '0') ){
                    
                    max = number.charAt(j) - '0';
                    idx = j;
                    
                } // inner if2
                
            } // inner for
            
            // 8. 찾은 최댓값을 sb에 더해준다.
            sb.append(max);
            
            // 9. 최댓값의 인덱스 ~ 현재 문자열의 마지막까지의 범위를 새로운 문자열로 갱신한다.
            number = number.substring( idx + 1, number.length() );
            
        } //for 

        return sb.toString();
        
    } // solution
    
} // end class

---

[ 참고한 블로그 ]

 

https://fbtmdwhd33.tistory.com/230

[프로그래머스,Level 2] 큰 수 만들기(JAVA 구현)