프로그래머스 Lv2 큰 수 만들기

문제 설명

어떤 숫자에서 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"

---

나의 풀이

나는 대체적으로 탐욕 알고리즘을 사용하는 문제들을 너무 어려워 하는 것 같다. 이번 문제도 오랜 고민 끝에도 문제를 해결하지 못하여 정답을 찾아볼 수 밖에 없었다 ㅜㅠ..

풀기 전에 접근했던 방법은 다음과 같다.

1. number.length() - k 를 한 문자열을 만든다.
2. 앞글자부터 비교하며 최대값을 찾으면 저장한다.
3. 최댓값 이전의 문자열들을 substring으로 잘라서 다시 비교를 시작한다.

우선은 위와 같은 방식으로 접근했는데, substring으로 잘라가며 비교를 하는 게 너무 비효율적이고 코드를 짜기도 쉽지 않았다.

그래서 찾아낸 코드의 접근법은 다음과 같다.

1. 최댓값을 담을 변수 max와 찾은 값의 인덱스를 저장할 변수 idx를 선언한다.
2. 위의 2번 까지의 과정을 2중 for문을 통해 앞에서부터 최댓값을 찾아간다.
   1. 여기서 첫 번째 for문의 범위는 number.length() - k 만큼이다.
   2. 두 번째 for문의 범위는 바깥 for문의 반복자 + k 만큼이다.
      1. 위에서 number.length() - k 까지만 돌기 때문에 그 이후의 문자열에 접근하기 위해서이다.
   3. 최댓값을 찾은 경우 max에 담아주고 해당 인덱스는 이미 조사했으니 해당 인덱스 + 1한 값을 idx에 담아준다.
3. 내부 for문이 종료되면 answer에 max 값을 담아준다.

class Solution {
    public String solution(String number, int k) {

        StringBuilder answer = new StringBuilder();

        int idx = 0;
        int max = 0;

        for (int i = 0; i < number.length() - k; i++) {
            max = 0;
            for (int j = idx; j <= i+k; j++) {

                if (max < number.charAt(j) - '0') {
                    max = number.charAt(j) - '0';
                    idx = j + 1;
                }
            }
            answer.append(max);
        }

        return answer.toString();
    }
}ㅇ

ㅇ