큰 수 만들기 : 그리디 (Level2)

이번문제는 생각하기 그리 어렵지 않은 문제이다. 다만, 구현하기가 은근히 까다로운 문제이다.

 

여기서 나의 풀이법에 대해 설명해 보겠다.

 

int count = 전체 길이에서 제거해야할 숫자를 뺴면, 구해야하는 숫자의 갯수를 알 수 있다.

 

가장 큰 값을 구해야하므로, 맨 앞자리 부터 하나씩 나올 수 있는 수 중, 가장 큰 값을 골라주면 된다.

 

(테스트케이스 3번)

"4177252841" 여기서 10-4= 6개의 수를 골라야한다. 숫자는 맨 앞자리가 가장 클 수록 큰 수이다.

 

그러므로 맨 앞자리로 올 수 있는 수는 "41772" 중 하나이다. 왜냐하면, 한자리를 고르고나면, 나머지 5자리도 골라 줘야하기때문에, 뒤에 5자리는 남겨두어야 한다. (맨 앞자리가 가장 크다면, 뒤에는 어떤 수가 와도 상관없기 떄문이다.)

 

가장 큰 7을 고르고 나면, 다음 수를 7뒤에서 부터 또 골라주기 시작한다. 

 

두번째 수에 올 수 있는 수는 "725" 중 하나이다. 이런 식으로 쭉  수를 골라주다가 뒤에 남은 수의 갯수를 모두 써야 되는 경우 그대로 붙여 주기만 하면 된다.

 

여기서의 핵심은 front 와 back의 인덱스이고, 마지막 문자열을 다 넣어줘야하는 부분이 핵심이다.

 

다른분은 스택으로 푼 방법도 있다. 역시 천재는 많은거 같다. 화이팅하자.

 

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        
        int len = number.length();
        
        int front = 0;      
        int count = len - k;
        int back = len - (count-1);
    
        int c = 1;
        while(c <= count){
            int max = -1; //초기화
        
            for(int i=front; i < back; i++ ){
                int num = Integer.parseInt(String.valueOf(number.charAt(i)));
                
                if(num == 9){ // 시간초과를 위한 IF문
                    max = num;
                    front = i+1; // 큰 수 다음으로 Index 이동 
                    break;
                }

                if(max < num){ // 큰수 찾기
                    max = num;
                    front = i+1; // 큰 수 다음으로 Index 이동 
                }
            }  
            back++; // 뒤로 하나 밀기
            c++; // 카운트 하나 증가
            
            answer+= max; // 글자 추가
            
            if(len-1-front == count - c){ // 뒤에 다 붙여야 되는 경우
                answer += number.substring(front, number.length());
                break;
            }
        }    
        return answer;
    }
}