[알고리즘][2] 큰 수 만들기

문제 설명
어떤 숫자에서 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"

나의 풀이

- stack 개념을 잘 이용해야 하는 문제

- 최선의 선택을 하기 때문에 그리디라 볼 수 있고 그리디와 스택은 관련성이 있다는 것을 배웠다.

def solution(number, k):
    # 가장 큰 수를 구해야하므로 그리디, DP, 탐색
    # 탐색의 경우 k=1, number의 자릿수가 1,000,000일 때 시간 초과 발생
    # 중간 결과물을 저장할 방법이 없으므로 DP도 X
    # 그럼 그리디
    # 스택 쓰면 된다.
    # 핵심 아이디어는 앞보다 더 큰 수가 나오면 앞을 제거하고 k의 개수를 늘려준다.
    # 그러다가 k의 개수가 최대가 되면 끝낸다
    # 왜냐하면 앞자리일 수록 중요도가 커지기 때문이다.
    # 앞과 같거나 작은 수가 나오면 스택에 넣어준다.
    
    stack = []
    cur_k = 0
    for idx, ele in enumerate(number):
        if not stack:
            stack.append(ele)
            continue
        
        while stack:
            peek = stack[-1]
            # 스택에 있는 제일 작은 원소와 비교하여 크면 제일 작은 원소를 제거. 이걸 반복
            if peek < ele:        
                stack.pop(-1)
                cur_k += 1
                # 만약 이미 다 제거했다면 뒤는 붙이기만 하면 된다
                if cur_k == k:
                    return ''.join(stack) + number[idx:]
            # 스택에 있는 제일 작은 원소보다 크지 않으면 끝낸다
            else:
                break
        
        # 현재의 원소를 stack에 추가하는 건 공통사항
        stack.append(ele)
        
    # k가 채워지지 않은 경우는 뒤에꺼부터 제거 왜냐하면 뒤로 갈수록 작아지기 때문
    return ''.join(stack[:-(k-cur_k)])

이건 이전의 풀이를 참고해서 리팩토링한 코드

- stack에서 pop하는 상황과 stack에 현재 원소를 넣는 상황 이 두가지 공통된 상황으로만 묶으면 된다.

- 특히 stack에 현재 원소를 넣는 건 어떤 경우에도 해당되기 때문에 조건문을 pop하는 상황으로 옮겨주면 된다.

def solution(number, k):
    # 가장 큰 수를 구해야하므로 그리디, DP, 탐색
    # 탐색의 경우 k=1, number의 자릿수가 1,000,000일 때 시간 초과 발생
    # 중간 결과물을 저장할 방법이 없으므로 DP도 X
    # 그럼 그리디
    # 스택 쓰면 된다.
    # 핵심 아이디어는 앞보다 더 큰 수가 나오면 앞을 제거하고 k의 개수를 늘려준다.
    # 그러다가 k의 개수가 최대가 되면 끝낸다
    # 왜냐하면 앞자리일 수록 중요도가 커지기 때문이다.
    # 앞과 같거나 작은 수가 나오면 스택에 넣어준다.
    
    stack = []
    cur_k = 0
    for idx, ele in enumerate(number):
        
        while len(stack) > 0 and stack[-1] < ele and cur_k < k:
            stack.pop(-1)
            cur_k += 1
        
        stack.append(ele)
        
    # k가 채워지지 않은 경우는 뒤에꺼부터 제거 왜냐하면 뒤로 갈수록 작아지기 때문
    if cur_k < k:
        stack = stack[:-(k-cur_k)]
    return ''.join(stack)