https://programmers.co.kr/learn/courses/30/lessons/42883
코딩테스트 연습 - 큰 수 만들기
programmers.co.kr
def solution(number, k):
answer = []
number = list(map(int, number))
start = 0
ans_len = len(number) - k
remain = ans_len - len(answer)
end = len(number) - remain + 1
while len(answer) < len(number) - k:
max_val = -1
temp_s = start
temp_e = end
remain = ans_len - len(answer)
# print((start, end))
# print(f'range is {number[start:end]}')
for i in range(temp_s, temp_e):
if number[i] > max_val:
start = i + 1
end = len(number) - remain + 2
max_val = number[i]
if max_val == 9:
break
answer.append(max_val)
# print(f'ans is {answer}')
# print()
return ''.join(map(str, answer))
print(solution('00100', 2))
# "87654321", 3, "87654"
# "18765432", 3, "87654"
# "77413258", 2, "774358"
# "12345678901234567890", 19, "9"
# "01010", 3, "11"
# "559913", 1, "59913"
# "9191919", 1, "991919"
# "00100", 2, "100"
처음엔 combinations 사용해서 한 줄로 끝내려 했는데 역시나 시간초과가 났다.
이 문제는 범위를 지정하는게 가장 중요하다.
예를들어
"4177252841" 에서 4 자리를 제거했을 때 가장 큰 수는 "775841" 이다.
"4177252841" 에서 4 자리를 제거하면 정답은 6자리 수가 된다.
6자리 수를 만들기 위해서 첫번째 가장 큰수를 찾아야하는 범위는
주어진 수(number) 의 처음부터 마지막 5자리를 뺀 범위 내에서 찾아야한다.
즉 "[41772]52841" 와 같이 대괄호 안에 있는 굵은 숫자들 중 하나를 찾아야한다.
왜냐하면 정답의 전체 자릿수가 6자리인데 첫번째 가장큰수를 주어진 수의 마지막 자리에서 찾는다면 더이상 찾을 큰 수 가 없어지기 때문이다.
탐색 범위는 항상 이전에 찾은 최대 값 다음부터 전체 글자수에서 아직 채워야할 남은 글자수를 뺀 곳 까지이다.
"[41772]52841" => 7
"417[725]2841" => 7
"4177[252]841" => 5
"417725[28]41" => 8
"41772528[4]1" => 4
"417725284[1]" => 1
보다 깔끔한 풀이
def solution(number, k):
stack = [number[0]]
for num in number[1:]:
while len(stack) > 0 and stack[-1] < num and k > 0:
k -= 1
stack.pop()
stack.append(num)
if k != 0:
stack = stack[:-k]
return ''.join(stack)