프로그래머스 : 탐욕법(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의 자릿수 미만인 자연수입니다.

 

나의풀이

from itertools import combinations
 
def solution(number, k):
    
    index_l = list(map(int, range(len(number))))
    num_l = list(number)
    perm_l = list(combinations(index_l,len(index_l)-k))
    answer = []
    
    for i in perm_l:
        
        transfer =''
        
        for j in i:
            
            transfer += num_l[j]
            
        answer.append(int(transfer))
    
    answer = str(max(answer))
  
    return answer

1. index 값에 대한 모든 combination 값을 구하고,(perm_l)

2. answer 에 k만큼 빠졌을때 생성될수 있는 모든 경우의수를 다 집어넣고,

3. 그중 최대값을 str 로 바꿔서 반환한다.

 

 

이렇게 풀어보았을때, 시간초과가 난다.

풀면서도 당연히 시간초과가 날것이라고 생각하였고, 역시나였다.

아마 2중 for문, combination 을통해 모든 경우를 구해서 이런 결과가 나왔을거라고 생각된다.

 

 

다른 사람 풀이를 살펴보자.

 

 

다른풀이

def solution(number, k):
    answer = [] # Stack
    
    for num in number:
        while k > 0 and answer and answer[-1] < num:
            answer.pop()
            k -= 1
        answer.append(num)
        
    return ''.join(answer[:len(answer) - k])

 

 

 

주요 Skill

1. append, pop

2. join

3. while k >0 and answer and answer[-1] < num:

 

 

answer = [] 일때,

while 문 자체를 돌리지 않기 위한 skill 로서 while answer 이라는 구문을 사용하였다.