[Level 2] 큰 수 만들기

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

 

def solution(num, k):
    max_num = []
    
    for i, n in enumerate(num):
        while len(max_num) > 0 and max_num[-1] < n and k > 0:
            max_num.pop()
            k -= 1
            
        if k == 0:
            max_num += list(num[i:])
            break
            
        max_num.append(n)
        
    max_num = max_num[:-k] if k > 0 else max_num
    
    return(''.join(max_num))

 

▷ 이 문제는 그리디 알고리즘을 이용하여 푸는 문제로, 주어진 문자열의 두 번째 숫자부터 이전의 숫자와 비교를 통해 가장 큰 숫자를 만들어 나가야 한다.

 

▷ 위 코드의 논리를 요약하면 다음과 같다.

 

1. max_num라는 빈 리스트를 만든다.

2. 주어진 문자열의 첫 번째 숫자는 반드시 max_num 리스트의 원소로 할당한다. 두 번째 숫자부터는 max_num 리스트의 마지막 숫자보다 크다면, 해당 숫자를 max_num 리스트에서 제거한다. 두 숫자의 비교 결과와 상관없이 해당 순서의 숫자를 max_num 리스트에 할당한다.

3. k 변수가 0이면 max_num 리스트를 문자열로 바꾸어 함수의 결과로 출력하고, 0이 아니라면 k 변수 만큼 오른쪽 끝부터 숫자를 제거한 것을 함수의 결과로 출력한다. 

 

▶ enumerate 함수는 첫 번째 인자의 값과 순서 정보를 for 문의 두 인자에 할당하는 역할을 한다.