[JAVA][Level2]PROGRAMMERS 큰 수 만들기

탐욕법을 이용해서 문제를 해결하는 문제

---

큰 수 만들기

---

문제 설명

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

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

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

제한사항

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

입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

주어진 문제

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        return answer;
    }
}

---

나의 문제풀이

class Solution {
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder(number);
        StringBuilder answer = new StringBuilder();

        for (int i = 0, index = -1; i < sb.length() - k; i++) {
            char max = 0;
            for (int j = index + 1; j <= k + i; j++) {
                if (max < sb.charAt(j)) {
                    index = j;
                    max = sb.charAt(j);
                }
            }
            answer.append(max);
        }

        return answer.toString();
    }
}

• number에서 k개를 제거한 크기만큼 반복한다. (return의 크기)
• 이중 for문으로 index를 0부터 사용하기 위해 index를 -1으로 초기화한다.
• return 크기만큼의 인덱스 중에서 가장 큰 수를 뽑아낸 후 마지막 인덱스까지 차례로 큰 수를 뽑아낸다.

10자리의 숫자에서 4자리를 제거했을 때 가장 큰 수를 만들려면 만들어야 하는 자릿수가 6자리이므로 처음에 확인할 수 있는 자리는 뒤에 숫자들이 가장 큰 숫자들이라고 생각을 해도 5자리까지는 확인이 가능해 앞에 5자리에서 가장 큰 수를 확인한 뒤 다시 가장 큰 숫자의 인덱스에서 다음 가장 큰 숫자의 인덱스를 확인하는 방법으로 반복하여 가장 큰 수를 뽑아냈다.
다른 사람들의 풀이를 봐도 모든 수를 비교해서 큰 수들을 뽑아내고 그 과정에서 효율적으로 뽑아내는가에 차이가 조금씩 있었다. 테스트 10에서 처리시간이 유독 느리게 나왔는데, 어딘가에 예외처리를 하면 될 거 같은데 아직은 어떻게 처리해야 할지는 잘 모르겠다.
그리디 알고리즘은 해 순간 당장의 최적의 상황만을 찾아 해답에 도달하는 방법인데, 이게 다른 알고리즘들이랑 다르게 먼가 개념적으로 이해가 잘 안돼서 해당 문제분류들을 좀 다양히 접해봐야겠다.

 

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/42883