[고득점 Kit(탐욕법)] 큰 수 만들기 (Python)

코딩테스트 연습 - 큰 수 만들기

 

풀이

 입력으로 주어진 number를 앞에서부터 탐색하면서 answer에 담아준다. 이때 현재 number의 숫자랑 answer에 담겨 있는 숫자를 하나씩 비교하여(역순으로) 현재 숫자가 answer에 담겨 있는 숫자보다 클 경우 answer의 숫자를 한자리씩 지워나간다. 

 예제의 "4177252841"로 살펴보면 다음과 같다.

1. 처음 숫자인 4를 answer에 담는다.
2. 이제 1과 answer를 한 자리씩 비교하는데 4보다 작으므로 1을 그래도 담는다. answer에는 41이 담겨져 있다.
3. 7과 answer를 역순으로 한 자리씩 비교한다. 
   • 7이 1보다 크므로 answer에서 1을 지운다. k는 1 감소
   • 다음으로 7과 4를 비교하는데 7이 더 크므로 answer에서 4를 지운다. k는 1 감소
   • 이제 answer에 숫자가 없으므로 7을 담아준다.
4. 위와 같은 방식으로 k가 0이 될 때까지 반복한다. 만약, number를 다 탐색했는데 제거해야 할 수가 남았다면 answer에 담긴 숫자의 마지막 k개를 지워주면 가장 큰 숫자가 된다.

 

 나는 구현할 때 answer를 아예 거꾸로 저장해놓고 마지막에 뒤집어서 리턴해줬는데 굳이 안그래도 될 것 같다.

 

 

코드

def solution(number, k):
    answer = number[0] # 처음에는 number의 첫 자리수를 먼저 넣어둔다.

    # 이제 1번 인덱스부터 number를 탐색한다.
    for i in range(1, len(number)):
        now = int(number[i]) # i번 인덱스의 숫자를 담아둔다.


        idx = -1 # answer의 0번 ~ idx번까지의 숫자를 제거한다.
        for j in range(0, len(answer)):
            # 더 이상 제거해야 할 숫자가 없거나 현재 number의 숫자보다 answer에 담긴 숫자가 크다면 탐색을 종료한다.
            if k == 0 or int(answer[j]) >= now:
                break 
            
            # 그렇지 않을 경우 answer의 숫자를 하나 제거한다. 
            k -= 1
            idx = j 
        
        # 이제 현재 숫자와 answer의 제거해야 할 숫자를 제거한 후 둘을 합쳐서 answer에 담아둔다.
        answer = number[i] + answer[idx+1:]

    # 아직 k가 남아있을 경우에는 answer의 마지막 k개 숫자를 제거해준다.
    if k != 0:
        return "".join(reversed(answer[k:]))
    else:
        return "".join(reversed(answer))