문제 풀기
효율적이지 않은 풀이(시간초과)
def deleted(number, k):
dlist = []
numbers= list(number)
n = len(numbers)
idxlist = combinations([i for i in range(n)],k)
for comb in idxlist:
filtered = [str(num) for i,num in enumerate(numbers) if i not in set(comb)]
dlist.append((''.join(filtered)))
return dlist
stack을 이용한 효율적인 풀이
def solution(number, k):
answer = ''
stk = []
for i in number:
while stk and stk[-1] < i and k>0:
k-=1
stk.pop()
stk.append(i)
return "".join(stk[:len(stk)-k])
회고 😎
- 모든 경우의 수를 확인해야 된다는 생각으로 접근하여 combination을 쓴 것이 비효율성을 낳았다.
- 핵심은 앞쪽에서부터 확인해서 작은 숫자들을 없애 나가는 것이다. 다시말해, k개를 앞에서부터 없애 나가도(Greedy하게 풀어도) 알고리즘 구현에 무리가 없다.
- "자릿수가 영향이 있는 수의 대소비교"를 할 때 greedy한 방법 및 stack을 복기해서 문제를 풀어 보자. 그것이 중요하다.