[99클럽 코테 스터디 20일차 TIL] 큰 수 만들기

💡문제

https://school.programmers.co.kr/learn/courses/30/lessons/42883

문제 설명

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

 

💡키워드

• 탐욕법(Greedy)

 

💡접근/해결 방법

처음에 문제를 보고 k개의 숫자를 제거하고 최댓값을 만드는 것은 number의 길이에서 k를 뺸 값만큼 조합을 만들고 그 가운데 가장 큰 값을 찾으면 된다고 생각했다.

그러나, 조합을 사용한 결과 시간초과가발생하였다. 그 코드는 아래와 같다.

⏰ 풀이1: 시간초과

from itertools import combinations

def solution(number, k):
  answer = ''
  answer_list = []
  # 만들어야할 숫자 개수 추출
  num_len = len(number) - k
  combination_list = list(combinations(number, num_len))
  for combi in combination_list:
    answer_list.append(''.join(combi))
  answer = max(answer_list)
  return answer

 

순열/조합은 값이 천만, 백만을 넘어가면 완전탐색에서 시간초과가 발생할 확률이 높다.

최종적으로 위의 코드의 시간복잡도는 이미 조합 생성부터 O(2ⁿ)이며, 최악의 경우 O(n X 2ⁿ) 이 된다.

 

시간 초과를 개선하기 위한 방법을 찾다 보니 스택을 사용하는 힌트를 얻었다.

접근 방법은 다음과 같다.

• 숫자의 각 자리를 순차적으로 확인하면서, 스택에 숫자를 넣거나 뺄지 결정한다.
• 스택을 사용하여 현재의 숫자가 이전 숫자들보다 큰 경우, 이전 숫자를 제거하여 더 큰 숫자를 만들 수 있도록 한다.
• 제거해야 할 숫자의 개수(k)가 다 채워질 때까지 이 과정을 반복한다.

 

✅ 풀이2: 스택

def solution(number, k):
    stack = []
    for i, num in enumerate(number):
        while stack and stack[-1] < num and k > 0:
            stack.pop()
            k -= 1
        stack.append(num)
    
    # k가 남아있다면 뒤에서 k개를 자릅니다.
    if k > 0:
        stack = stack[:-k]
    
    return ''.join(stack)

 

코드에 대해 단계별로 보면 다음과 같다.

1. 초기화:
   • 빈 스택(stack)을 초기화한다. 이 스택은 최종 결과를 만들기 위한 숫자들을 저장하는 데 사용된다.
2. 숫자 순회:
   • 주어진 숫자의 각 자리(num)를 순차적으로 검사한다.
3. 스택 관리:
   • 현재 숫자(num)가 스택의 마지막 요소(stack[-1])보다 크고, 제거할 수 있는 숫자의 개수(k)가 남아있는 경우:
     • 스택의 마지막 요소를 제거(pop())한다. 작은 숫자를 제거하여 이후에 더 큰 숫자를 만들 수 있도록 하기 위해서다.
     • 제거할 수 있는 숫자의 개수(k)를 하나 줄인다.
   • 현재 숫자(num)를 스택에 추가한다.
4. 남은 숫자 제거:
   • 위의 과정을 마친 후에도 제거할 숫자(k)가 남아 있다면, 스택의 끝에서부터 k개의 숫자를 제거한다.
   • 제거하지 못한 숫자들을 처리하기 위해서다.
5. 결과 생성:
   • 스택에 남아있는 숫자들을 합쳐서 최종 결과를 반환한다.