프로그래머스_큰 수 만들기

1. 문제

출처 : 프로그래머스

2. 소스코드

def solution(number, k):     answer = ''     number = list(number)     stack = []     for n in number:         while stack and stack[-1] < n and k:             stack.pop()             k -= 1         stack.append(n)       if k:         stack = stack[:-k]              return ''.join(stack)

3. 고찰

1) 스택 이용

새로 원소를 추가할 때 바로 앞 원소와만 비교를 하기 때문에 스택이용이 가능하다.

 

2) 알고리즘

문자열인 number를 문자 리스트형태로 바꿔주었다. (하나씩 for문을 돌리기 위함. 이렇게 하지 않고, 먼저 스택에 첫번째 숫자를 넣어준 뒤 for num in number[1:]: 이렇게 for문 돌리는 것도 가능함.)

stack변수를 빈 리스트로 만들어준다.

for문을 돌리면서 number의 각 자리수에 대하여

    스택이 비어있지 않으면서 & 자신보다 더 작은 숫자가 들어가 있으면서 & k>0을 만족하면

        스택을 pop하고 k를 -1해준다.

    스택에 자기 자신을 push

for문을 다 돌린 후에 k가 0이 아니라면

    뒤에서부터 k자리만큼 빼준다.

남아있는 수들을 문자열형태로 바꾸어 리턴한다.

 

3) 시간복잡도

python의 pop()함수는 O(1)이다.

따라서 number의 자리수가 N이라 하면, 하나의 for문을 돌리므로 해당 코드의 시간복잡도는 O(N)이다.