[알고리즘][X] 큰 수 만들기
2023. 7. 10. 12:06ㆍ알고리즘 풀이
문제 설명
어떤 숫자에서 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"
나의 풀이
- 틀린 풀이
- 10번에서 시간 초과가 난다.
- 재귀의 한계일지도...
- 재귀는 안쓰는게 옳다.
import sys
sys.setrecursionlimit(10000)
complete_number = ""
def solution(number, k):
result_num = len(number) - k
def recursive(number, num_complete_number):
global complete_number
if num_complete_number == result_num:
return
max_number = number[0]
idx = 0
for i, ele in enumerate(number):
if ele == "9":
max_number = "9"
idx = i
break
elif max_number < ele:
max_number = ele
idx = i
right_rest = len(number) - idx - 1
if right_rest > (result_num - num_complete_number - 1):
complete_number += number[idx]
recursive(number[idx+1:], num_complete_number + 1)
elif right_rest == (result_num - num_complete_number - 1):
complete_number += number[idx:]
return
else:
recursive(number[:idx], num_complete_number + len(number) - idx)
complete_number += number[idx:]
recursive(number, 0)
return complete_number
- 참고한 풀이
- 제거할 수 있는 개수가 정해져 있는 것과 제일 앞의 자리가 중요하다는 게 핵심이다.
- 그리디는 O(n)으로 풀 수 있다.
def solution(number, k):
stack = []
for ele in number:
# stack의 원소들을 제거할 수 있는 조건
while len(stack) > 0 and stack[-1] < ele and k > 0:
stack.pop()
k -= 1
stack.append(ele)
if k > 0:
stack = stack[:-k]
return ''.join(stack)
'알고리즘 풀이' 카테고리의 다른 글
[알고리즘] 섬 연결하기 (0) | 2023.07.12 |
---|---|
[알고리즘] 구명보트 (0) | 2023.07.11 |
[알고리즘][X] 조이스틱 (0) | 2023.07.09 |
[알고리즘][X] 체육복 (0) | 2023.07.07 |
[알고리즘] 모음사전 (0) | 2023.07.06 |