[프로그래머스] 큰 수 만들기 (Python) - Greedy, 시간초과 해결

문제 설명

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

---

def solution(number, k):
    answer = ''
    # number = [int(x) for x in list(number)] **시간초과 해결: 형변환 해주지 않아도 됨
    
    #정답의 길이. number길이가 5이고 k=2 일 경우 정답은 3자리
    need_len = len(number) - k 
    
    for i in range(need_len):
        #limit = 끝에 최소 몇자리 제외하고 max값을 구해야 하는지.
        #number 1924, answer len 2 의 경우 첫번째 max는 192에서 골라야 2자리 만들 수 있음
        #현재 number의 길이 - 추가로 더 구해야 할 answer의 길이 까지 보고 max 값 구해야 함
        limit = len(number) - (need_len-i)
        search = number[:limit+1]
        
        if '9' in search: #**시간초과 해결: 9가 있을 경우 패싱
            max_num = '9'
            answer += max_num
        else:
            max_num = max(search)
            answer += max_num
        
        number = number[number.index(max_num)+1:] #append 한 숫자 다음 부분부터 반복
        
    return answer

푼 건 40분인데, 시간초과 때문에 무려 약 1시간을 고민한 문제 ......

관건은 두가지 였다

1) 9번 테케 해결: 형변환의 경우 number의 길이가 길 때 문제가 발생하고, 형변환 해주지 않아도 되는 문제였으므로 해당 부분 삭제

2) 10번 테케 해결: 9가 있을 경우 max 해주지 않고 바로 추가해야 시간 초과 안됨...

 

이런 자잘한 것으로 시간초과를 해결한다니

아주 놀라운 아주 짜증난 문제였다 ㅎㅎ

 

이 외 limit으로 끝에 몇자리를 제외하고 max를 구할 지 생각해내는 것은 쉬웠으나

그 limit을 가지고 어떻게 number를 slicing 해야 하는지 푸는 것은 어려웠음... 

number[ : -n] 이렇게 slicing 하려고 하니 자꾸 맨 마지막 숫자를 구할 때 number[ : -0] 이 들어가서 에러가 발생했던 ㅎ

 

오늘도 질문하기 탭을 아주 유용하게 활용한 바보같은 나...

잘하자 발전하자