[웅's 프로그래머스] 큰 수 만들기 - 파이썬(python) 풀이

주어진 number 에서 k 자리수를 제외하여 큰 수를 만드는 문제이다.

어떤 수가 만들어 지든지 간에 k 자리수를 제외하면 결국 남는 number 의 자리수는 동일하다.

그렇다면 가장 큰 수란? 앞자리가 1이라도 더 큰 수가 가장 큰 수이다!

 

이 문제를 풀며 배운 점은, 앞자리와 뒷자리를 계속 비교해야 하는 로직에는 Stack 자료구조를 사용해야 한다는 점이다.

 

즉 나는 stack 에 number 를 차곡차곡 쌓으면서 만약 스택의 가장 상단에 위치한 값보다 큰 값을 넣는 경우에는 최상단 값을 삭제하는 논리로 문제를 풀었다. 

 

중요한 점은 최상단 값을 삭제하고 다시 넣으려고 할 때, 다시 최상단 값과 넣는 값을 비교하여 넣는 값이 클 경우에는 위 과정을 반복하도록 했다.

 

이러한 반복문이 끝나는 시점은 삭제를 k 번 다 한 경우 이거나, 최상단 값이 넣으려는 값보다 클 때이다.

 

만약, 이러한 stack 에 넣는 과정을 다 거쳤음에도 k 번 삭제가 되지 않았다면 내림차순으로 정렬되었다는 이야기 이므로 마지막에 k 개를 삭제한다.  

 

def solution(number, k):
    stack = []
    for i in range(len(number)):
        curr = number[i]
        while 1:
            if len(stack)==0:
                stack.append(curr)
                break

            prev = stack.pop()
            
            if curr > prev :
                k -= 1

            else :
                stack.append(prev)
                stack.append(curr)
                break

            if k == 0:
                return ''.join(stack)+number[i:]
        
    if k>0:
        return ''.join(stack[:-k])