ex) 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있음
이 중 가장 큰 숫자는 94
number: 문자열 형식인 숫자
k: 제거할 수의 개수
number에서k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return
제한 조건
number는 2자리 이상, 1,000,000자리 이하인 숫자
k는 1 이상 number의 자릿수 미만인 자연수
"""
입출력 예시)
number = "1924", k = 2 -> "94"
number = "1231234", k = 3 -> "3234"
number = "4177252841", k = 4 -> "775841"
"""
## 의사코드 ##
# number에서 k개의 수를 제거했을 때 나올 수 있는 경우 구하기
# combinations(number, len(number)-k))
# combinations로 구한 값들 중 max()를 문자열 형태로 return
첫 번째 시도
from itertools import combinations
def solution(number, k):
numbers = list(map(int, number))
# number에서 k개의 수를 제거했을 때 만들 수 있는 조합
combi = list(combinations(numbers, len(number)-k))
max_n = map(str, max(combi))
return ''.join(max_n)
-> combinations로 조합 구현
-> 추가 테스트 케이스 실패 (시간 초과)
두 번째 시도
def solution(number, k):
numbers = list(number)
n = len(numbers)
r = len(number) - k # number에서 k개의 수를 제거한 숫자의 길이
combi = [] # number에서 k개의 수를 제거했을 때 만들 수 있는 조합
# DFS 수행
def dfs(idx, li):
if len(li) == r:
combi.append(li[:])
return
for i in range(idx, n):
dfs(i+1, li+[numbers[i]])
dfs(0, [])
return ''.join(max(combi))
-> DFS로 조합 구현
-> 추가 테스트 케이스 실패 (시간 초과, 런타임 에러)
통과한 코드
def solution(number, k):
stack = []
for num in number:
if len(stack) == 0:
stack.append(num)
continue
if k > 0:
while stack[-1] < num:
stack.pop() # stack[-1]을 꺼냄
k -= 1
if len(stack) == 0 or k <= 0:
break
stack.append(num)
stack = stack[:-k] if k > 0 else stack
return ''.join(stack)
-> stack 활용, 앞자리에 큰 숫자가 와야 전체 수를 크게 만들 수 있다는 점 활용
과정 확인
number = "1231234"
k = 3
"""
k = 3일 때
num: 1
stack: ['1']
num: 2
k: 3
stack: ['1']
stack[-1]: 1
stack[-1](=1) vs num(=2)
stack[-1] < num 인 경우
pop한 stack: []
k: 2
stack.append(num): ['2']
num: 3
k: 2
stack: ['2']
stack[-1]: 2
stack[-1](=2) vs num(=3)
stack[-1] < num 인 경우
pop한 stack: []
k: 1
stack.append(num): ['3']
num: 1
k: 1
stack: ['3']
stack[-1]: 3
stack[-1](=3) vs num(=1)
k: 1
stack.append(num): ['3', '1']
num: 2
k: 1
stack: ['3', '1']
stack[-1]: 1
stack[-1](=1) vs num(=2)
stack[-1] < num 인 경우
pop한 stack: ['3']
k: 0
stack.append(num): ['3', '2']
num: 3
k: 0
stack.append(num): ['3', '2', '3']
num: 4
k: 0
stack.append(num): ['3', '2', '3', '4']
stack: ['3', '2', '3', '4']
stack[:-k]: ['3', '2', '3', '4']
'3234'
"""
다른 풀이
def solution(number, k):
answer = [] # Stack
for num in number:
while k > 0 and answer and answer[-1] < num:
answer.pop()
k -= 1
answer.append(num)
return ''.join(answer[:len(answer) - k])
