[Java][프로그래머스][Level 2] 큰 수 만들기

문제 설명

문제 설명

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

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

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

 

제한 조건

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

입출력 예

number                                          k                                                 return

1924	2	94
1231234	3	3234
4177252841	4	775841

 

생각

저번에 풀었다가 포기한 문제이다. 아예 생각의 전환을 바꾸고 규칙성을 찾아보기로 하였다. 4177252841로 예시를 들어보자. 가장 큰 수를 만들어야 하므로 맨 앞에는 가장 큰 숫자가 와야한다. 앞의 숫자보다 바로 뒤의 숫자가 크면 앞의 숫자를 제거하는 규칙을 사용하였다. 그러면 4177에서 7보다 4와 1이 작으므로 삭제한다. 그러면 77252841이 된다. 또 5보다 2가 작으므로 2를 삭제한다. 7752841이 된다. 이제 다시 8보다 2가 작으므로 2를 삭제하면 775841이 되고 삭제한 수가 4개가 되므로 종료한다.

 

이렇게 되면 같은 숫자, 예를 들어 1000000 이고 k=3일때가 문제가 된다. 위 경우에는 일단 끝까지 탐색을 하므로 i가 끝까지 갔을 때, 전의 숫자와 지금의 숫자가 같으면 맨 뒤의 숫자를 삭제하는 방식을 사용하였다. 자세한건 주석으로 설명하겠다.

 

코드

import java.util.*;
 
class Solution {
    public String solution(String number, int k) {
        //빠른 연산을 위해 StringBuilder을 사용했다.
        StringBuilder sb = new StringBuilder(number);
        int delete_count = 0;
        int index = 1;
        
        while(delete_count != k) {
            //전의 숫자와 비교해야 하므로 index는 1부터 시작한다.
            //전의 숫자보다 더 크면 전의 숫자를 삭제하고 크기가 줄어들었으므로 index를 줄여준다.
            if(index>=1 && sb.charAt(index) > sb.charAt(index-1)) {
                sb.deleteCharAt(index-1);
                index--;
                delete_count++;
            } else {
                //index가 맨 끝으로 가고, 그 전의 숫자와 작거나 같으면 지금의 숫자를 삭제해준다.
                if(index==sb.length()-1 && sb.charAt(index) <= sb.charAt(index-1)) {
                    sb.deleteCharAt(index);
                    delete_count++;
                    index--;
                } else {
                //그 외의 경우에는 index를 추가해준다.
                index++;
                }
            }
        }      
        return sb.toString();
    }
}