[고득점 kit]_탐욕법_#3. 큰 수 만들기

(문제 설명)

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

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

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

제한 조건

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

입출력 예numberkreturn

"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

---

(문제 해설)

 

그림으로 설명하겠습니다.

참고로 말하기 전에 전체 최댓값이 되는 값을 찾지만 순서 변경을 용인하지 않는 상황이기 때문에 조합을 이용해 풀 수 없습니다. 머 또 어떤 조건을 부여하여 풀 수 있을지도? 나는 몰루? 모르겠지만 단순하게 조합을 이용하는 건 안됩니다.

 

그림1_생각 알고리즘 설명

짚고 넘어가기)

0. 찾으려는 전체 길이 생각

1. 초기 구간 설정에 대해 생각

2. 그다음 찾을 경우 구간의 변화에 대해 생각

--> 이를 고려하여 풀면 된다.

 

---

[ 코드 ]

 

def solution(number, k):
    answer = ""
    length = len(number) - k
    st = 0
    end = k + 1
    max_idx = -1

    for i in range(length):
        # print(st, end, answer)
        max_num = -1
        for idx in range(st, end):
            # print(max_num, end=" ")
            if int(number[idx]) == 9:
                max_num = number[idx]
                max_idx = idx
                break
            if int(number[idx]) > int(max_num):
                max_num = number[idx]
                max_idx = idx
      
        answer += max_num
        st = max_idx + 1
        end += 1

    return answer

 

혹시 그림 설명에서 예제 3의 진행 상황을 보고 싶은데 하는 사람은 제가 주석으로 처리한 print문을 풀면 알 수 있습니다.

 

---

후기

 

좋은 그리디 문제 같다

어떻게 최적의 상황으로 문제를 풀어야 할지

고려해보는 생각을 할 수 있게 해주는 좋은 문제