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 함수를 완성하세요.
제한 조건 & 입출력 예
def solution(number, k):
answer = ''
number = list(number) # number 배열을 리스트화
stack = [number.pop(0)] # number 배열의 첫 번째 요소를 result에 삽입 (괄호 안에 입력한 번호를 인덱스로 가지는 요소가 pop됨)
for n in number:
if stack[-1] < n: # result의 가장 마지막 값이 n보다 작으면
while stack and stack[-1] < n and k > 0:
stack.pop() # 괄호 안에 아무런 숫자 없이 배열을 pop하면 뒤에서부터 값이 삭제됨
k -= 1
stack.append(n) # result 배열의 뒤에서부터 n보다 작은 숫자들을 모두 제거한 후, n 값을 삽입
elif k == 0 or stack[-1] >= n:
stack.append(n) # 바로 n 값을 삽입
if k > 0: # 아직 k개의 수가 제거되지 않은 경우
stack = stack[0:-k] # 뒤에서부터 제거
answer = ''.join(stack)
return answer
실행 결과
- 시간이 오래 걸리는 테스트 케이스들이 간혹 보여 이를 줄일 수 있는 방법을 더 찾아봐야겠다.
코드 및 문제풀이 아이디어
위 블로그에 문제 풀이 아이디어와 슈도 코드, 직접 구현한 코드에 대한 설명이 아주 잘 나타나있다. (나중에 문제 풀이 방법을 잊어버리게 되면 해당 글을 통해 다시 보자!)