[프로그래머스][그리디] 큰 수 만들기
def solution(number, k):
answer = []
for num in number:
while answer and k>0 and answer[-1]<num:
answer.pop()
k-=1
answer.append(num)
if k>0:
answer=answer[:-k]
return ''.join(answer)
- 풀이
- 1. 숫자를 왼쪽부터 순차적으로 탐색하며 스택에 쌓는다.
2. 새로운 숫자를 넣을 때, 스택에 나보다 작은 숫자가 있다면 그 숫자를 제거하고(k 감소) 내가 그 자리를 대신한다.
3. 반복: 나보다 큰 숫자를 만나거나 k가 0이 될 때까지 앞의 숫자들을 연쇄적으로 지운다.
4. 예외: 전체 탐색 후에도 k가 남았다면, 뒤에서부터 남은 k만큼 잘라낸다 (이미 내림차순인 경우). - 시간 복잡도: O(n)인 이유
• 분할 상환 분석(Amortized Analysis) - : for문 안에 while문이 있어 O(n^2)처럼 보일 수 있으나,
- 모든 숫자는 스택에 딱 한 번 들어가고(Push), 최대 한 번 나간다(Pop).
• -> 전체 연산 횟수는 최대 2n을 넘지 않음 - O(n^2) 이러면 매번 전체를 돌아야함
- 하지만 이 로직은 앞에서 제거하면 다시 돌지 않음
- 각 값은 들어오고/나가고 2번의기회뿐 -> O(2n)