[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
개의 원소를 제거한다.
스택을 문자열로 바꿔 해당 값을 리턴한다.
결과
해당 방식이 내가 푼 방식보다 훨씬 효율적이다.
Author And Source
이 문제에 관하여([Programmers] Greedy - 큰 수 만들기 (Python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@deannn/Programmers-Greedy-큰-수-만들기-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)