🔥[99클럽 코테 스터디] 20일차 TIL - 큰 수 만들기

⏳문제

어떤 숫자에서 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) {
        StringBuilder str = new StringBuilder(number);
        int temp = 0;
        int max = 0;

        for (int i = 0; i < k; i++) {
            for (int j = 0; j < str.length(); j++) {
                char temp1 = str.charAt(j);
                temp = Integer.parseInt(str.deleteCharAt(j).toString());
                
                if (temp > max) {
                    max = temp;
                }
                str.insert(j, temp1);
            }
            str.delete(0, str.length());
            str.append(max);
            

            max = 0;
        }

        
        return str.toString();
    }
}

그러나 거의 모든 테스트 케이스에서 런타임 에러가 발생하였다.

이중 for문을 돌면서 필요하지 않은 부분까지 탐색했기 때문이라고 생각했다.

두 번째 시도

그래서 다른 규칙을 찾아보았다.

큰 수를 만들기 위해서는 큰 수가 맨 앞자리에 와야 한다.
하지만, 입력 값이 예를 들어 "4177252841"과 4라면, 8이 맨 앞에 올 수는 없다. 왜나하면, 문자열의 순서가 바뀌어서는 안되고, 8아래에는 2자리 뿐이기 때문이다.

이의 특성을 활용해 맨 앞에서 k번째까지의 숫자 중에서 최소값을 하나씩 지워가면 되겠다는 생각이 들었다.
그렇게 되면, 순서와 자릿수를 지키면서 앞자리가 제일 커질 수 있겠다고 생각했다.

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

        for (int i = 0; i < k; i++) {
            int minIndex = 0;
            char min = str.charAt(0);
            for (int j = 0; j < k; j++) {
                char temp = str.charAt(j);
                if (temp < min) {
                    minIndex = j;
                    min = temp;
                }
            }
            str.deleteCharAt(minIndex);
        }

        
        return str.toString();
    }
}

결과는 마찬가지로 대부분의 경우에서 런타임 에러가 발생하거나 실패하였다.

이는 로직에 오류가 있었다. 현재 코드에서는 k번 반복하면서 매번 가장 작은 숫자를 찾고 삭제하고 있는데, 그러나 문제의 요구사항은 가장 큰 숫자를 만들기 위해 가장 작은 숫자를 제거하는 것이 아니라, 현재 숫자와 다음 숫자를 비교하여 더 큰 숫자를 남기는 것이다. 즉, 삭제할 숫자를 선택할 때, 다음 숫자와 비교하여 더 큰 숫자를 남기는 방식으로 접근해야 한다.

그래서 코드를 싹 엎고, 해당 방식으로 다시 접근을 해 보았다.

마지막 시도

매번 최대값을 만들 수 있는 최선의 선택을 어떻게 할 수 있을까 고민하다가 한 가지 방법을 생각해냈다.

입력 number의 길이가 만약 10이라면,
0번 부터 3번 인덱스까지의 요소 중 최대값이 최종 반환값의 첫 번째 자리가 되어야 한다.

왜나하면, 4번 부터 9번 인덱스까지의 요소들 중에서는 어떠한 값도 첫 번째 자리수가 될 수 없기 때문이다.

예를 들어, number가 "4177252841"이라면
뒷자리 "252841"에서는 어떤 값을 고르더라도 자릿수에 의해 정답의 첫 번째 값이 될 수 없으므로,
앞자리 "4177"에서 가장 큰 값이 정답의 첫 번째 자리 수가 되어야 한다.
그러면 앞의 "41"은 날아가게 되고, 3번째 인덱스의 7을 answer에 추가함으로써 첫 번째 사이클이 완료된다.

두 번째 사이클에서는 "7252841"에서 시작하게 되고,
마찬가지로 "725"중에서 최대값을 찾아 answer에 이어붙여야 한다.

이제, 이를 코드로 옮기는 것이 중요한데,
어떻게 하면 인덱스를 잘 활용할 수 있을 지 고민이 많았다.

👾최종 코드

class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();
        int startIdx = 0;
        int answerLength = number.length() - k;
        int count = 0;
        
        for (int i = 0; i < answerLength; i++) {
            int max = 0;
            for (int j = startIdx; j <= i + k; j++) {
                if (number.charAt(j) - '0' > max) {
                    max = number.charAt(j) - '0';
                    startIdx = j + 1;
                }
            }
            answer.append(Integer.toString(max));
            count++;

        }

        return answer.toString();
    }
}

그래서 구해야 하는 answer의 길이만큼 반복을 돌면서 탐색을 시작해 나갈 number의 첫 번째 인덱스를 startIdx로 하나 선언해 주었다.

그리고, startIdx부터 i + k까지 즉, 최대값으로 가져올 수 없는 배열의 뒷부분 바로 앞까지의 범위 중에서 최대값을 찾고 answer에 하나씩 append해주는 방식으로 구현을 하니 마침내 문제를 해결할 수 있었다.

---

🔗문제 링크
💻Repository