문제
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한사항
- number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
- k는 1 이상
number의 자릿수미만인 자연수입니다.
입출력 예 설명
접근
아이디어가 생각이 나지않아 구글링해서 참고를 했다
스택을 이용한 방식이며 원리는 아래와 같다.
스택에 주어진 배열의 첫번째 값을 넣고, 배열의 인덱스 1부터 끝까지 반복을 하면서 스택맨 위의 값과 비교를 한다.
비교했을때 스택의 값이 배열의 값보다 작다면 스택의 값을 pop()하고 k를 -1한다.
스택의 크기가 0이 되고 스택의 맨위 값이 배열의 값보다 크거나 같아지고 k의 값이 0이 될때까지 반복해서 스택의 맨밑에 큰값이 오도록 한다.
k를 빼면서 0일때까지 확인하는 이유는 문제에서 k개 만큼 제거한다 했으므로 이를 체크해주는 것이다.
이렇게 pop()하고 k-=1 하는 과정이 끝나면 배열의 값을 스택에 넣어준다. 이를 배열의 끝까지 반복을 하면서 스택을 채워준다.
스택에서 (배열의 크기 - k )개 만큼의 숫자가 필요하다(k개 만큼 제거한 수라고 했기때문)
이를 위해서 반복문을 이용해 스택의 크키가 원하는 수인 (배열의 크기 - k) 까지 pop()을 해주고 최종적으로 join을 이용해 스택의 값을 붙여서 문자열로 만들어서 리턴해준다.
def solution(number, k):
result_len = len(number) -k
number = list(number)
stack = [number[0]]
for i in range(1,len(number)):
while len(stack) > 0 and stack[-1] < number[i] and k>0:
stack.pop()
k-=1
stack.append(number[i])
while len(stack) > result_len:
stack.pop()
return ''.join(stack)결과
