[프로그래머스] '큰 수 만들기' 알고리즘 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석
   
   [Most 1 의 풀이]

---

 

문제 설명

 

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

 

 

알고리즘 분석

 

• Most1의 풀이

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
    	# stack과 k가 0보다 크고, stack의 마지막 요소가 num보다 작을 경우 반복 
        while len(stack) > 0 and k > 0 and stack[-1] < num:
            k -= 1 
            stack.pop() # stack의 마지막 요소를 제거
        stack.append(num) # stack에 num 추가 
    if k > 0: # k가 0보다 클 경우
        stack = stack[:-k] # stack을 뒤에서부터 k만큼 제외
    return ''.join(stack)

 

앞에서부터 순차적으로 확인하기 위해서 스택을 사용한 풀이 

 

적절하게 스택을 이용해주어서 런타임 시간이 굉장히 짧다. 

 

 

programmers.co.kr/learn/courses/30/lessons/42883

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