큰 수 만들기

문제 설명

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

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

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

 

제한 조건

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

---

문제 풀이

풀이 1(시간 초과)

입출력 예 3번을 토대로 설명한다면 숫자를 4개를 삭제하여 제일 큰 수를 만들어야 합니다.

이때 앞에서 부터 4+1개 까지 안에서 1개 이상은 무조건 남아있어야 합니다.

숫자 4개를 전부 앞에서 빼더라도 1개는 남기 때문입니다.

그렇기에 4+1개 중 제일 큰 숫자가 맨 앞자리가 되어야 만들어진 숫자가 제일 커집니다.

그러므로 41772 중에 세 번째 7이 맨 앞자리가 되어야 하고 앞에 4,1 두 개가 빠집니다.

그 후 남은 7252841 중에 다시 2+1개 중 제일 큰 숫자를 찾는 방식을 반복하면 return값을 얻을 수 있습니다.

 

해당 풀이과정을 소스코드로 구현했지만 시간 초과가 나왔기 때문에 다른 방식으로 다시 풀었습니다.

 

 

풀이 2

3번째 예시 풀이

구역을 나누고 작은 수부터 제거하는 방식

우선 앞에서부터 for문을 통해 바로 앞 숫자보다 커지는지 위치를 확인하여 ArrayList에 담았습니다.

그 후 해당 위치에서 앞에 숫자가 더 작으면 삭제합니다.

위 그림을 보시면 1이 7보다 작기 때문에 제거, 4도 작으므로 제거

그 후 앞에 아무것도 없으므로 두 번째 위치인 5로 이동해 앞에 2를 제거, 그 앞에 7은 5보다 크므로 

다음 위치인 8로 이동 8에서 앞에 숫자인 2를 제거하면 총 4개를 전부 제거했으므로 

결과를 반환하면 됩니다.

 

 

아래는 K가 4보다 크다면 어떤 숫자를 삭제하게 되는지 보여주는 그림입니다.

아래는 해당 개념을 구현한 코드입니다.

개념을 단순하게 코드화했기 때문에 불필요한 부분이 있을 수 있습니다.

 

public static String solution(String number, int k) {
    String answer = "";
    StringBuilder sb = new StringBuilder(number);
    ArrayList<Integer> bigger = new ArrayList<>();
 
    for (int i = 1; i < number.length(); i++) {
        if (number.charAt(i - 1) < number.charAt(i)) {
            bigger.add(i);
        }
    }
 
    int idx = 0;
    int cur_idx = 0;
    int rm = 0;
    while (k > 0) {
        if (idx >= bigger.size()) {
            sb.deleteCharAt(sb.length() - 1);
            k--;
        } else {
            cur_idx = bigger.get(idx) - rm;
            if (cur_idx - 1 < 0 || sb.charAt(cur_idx - 1) >= sb.charAt(cur_idx)) {
                idx++;
            } else {
                sb.deleteCharAt(cur_idx - 1);
                k--;
                rm++;
            }
        }
    }
    answer = sb.toString();
    return answer;
}