[프로그래머스] 큰 수 만들기

 

문제 설명

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

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

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

제한 사항

-number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.

-k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예

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

접근법

이 문제는 탐욕법(Greedy)입니다! 먼저 바꿔야할 개수 k번 만큼 반복문을 돌고, number의 문자 하나하나에 접근하며, 현재 문자와 다음 문자를 비교하고, 다음 문자가 더 클경우 현재 문자를 지워버립니다. 만약 현재 문자보다 큰 문자가 없을 경우 문자열의 가장 뒷부분을 지워버립니다! 여기서 else문이 for문과 함께 쓰였는데, 파이썬에서 for문이 break에서 끊기지 않고 끝까지 돌았다면, else문을 수행합니다.

start 와 len_number를 계속 갱신해주는 이유는, 문자열에서 하나의 문자가 지워지면, 문자열의 길이가 짧아지기 때문이죠! 그래서 인덱스, 길이 모두 바뀝니다!

​

나의 코드

def solution(number, k):
    len_number = len(number)
    start = 0
    for count in range(k):
        for index in range(start, len_number-1):
            if number[index] < number[index+1]:
                number = number[:index] + number[index+1:]
                len_number -= 1
                if index > 0: start = index-1
                break
        else:
            number = number[:len_number-k+count]
            break
    return "".join(list(map(str,number)))