[Programmers] Greedy - 큰 수 만들기 (Python)
Greedy: 큰 수 만들기 [Lv2]
문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한사항
- number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
- k는 1 이상 number의 자릿수 미만인 자연수입니다.
입출력 예
| number | k | return |
|---|---|---|
| "1924" | 2 | "94" |
| "1231234" | 3 | "3234" |
| "4177252841" | 4 | "775841" |
Solution
내 풀이
def solution(number, k):
number = list(number)
for i in range(k):
for j in range(len(number) - 1):
if number[j] == '9':
continue
if number[j] == '0' or number[j] < number[j+1]:
number.pop(j)
break
else:
remain = k - i
number = number[:-remain]
break
return str.join('', number)
결론부터 얘기하면 실패했다. 테스트케이스 하나가 시간초과가 났다. 이걸 해결을 못함..
일단은 내가 푼 방법을 설명하자면 2중 for문을 사용해서 number의 숫자들을 각각 비교하는 방법이다.
number[j]와 number[j+1]을 비교해서 number[j+1]이 더 크면 number[j]를 없애는 방식으로 총 k개를 없앤다.
몇가지 경우를 더 줄여 for문을 빠르게 돌리기 위해서, number[j]가 9인 경우에는 바로 다음 숫자로 넘어가고, 0이면 없앤다.
안쪽 for문이 정상적으로 종료된다면 숫자를 끝까지 다 비교한 것이므로, k개 만큼 다 빼지 못했을 수도 있다. 그러므로 더 빼야할 수(k-i)만큼 number의 끝에서 슬라이싱한다.
결과
위의 사진에서 보듯이, 8번 테스크케이스가 시간이 오래 걸렸고, 10번은 시간 초과가 나왔다.
Best Code
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)그리디 문제이지만 스택을 사용했다. 처음에 스택에 원소 하나를 넣고 number에서 하나씩 가져와서 이를 스택의 마지막 원소와 비교하는 방법이다. 원소를 하나 뺄 때마다 k를 1씩 빼서 k가 0이면 모두 뺀 것이다.
while문을 사용해서 스택에 원소가 있고 k가 0보다 크고 스택의 마지막 원소가 number에서 가져온 값(num)보다 작다면 k를 1 빼고 스택의 마지막 원소를 없앤다(pop())
while문을 빠져나오면 num을 스택에 넣어준다.
위와 같은 방식 for문을 통해 num을 number의 1번 인덱스 값부터 끝까지 반복한다.
for문이 끝나면 k가 0보다 큰지 비교한다. 0보다 크다면 스택에서 마지막에서 k개의 원소를 제거한다.
스택을 문자열로 바꿔 해당 값을 리턴한다.
결과
해당 방식이 내가 푼 방식보다 훨씬 효율적이다.
