[프로그래머스][탐욕법] 큰 수 만들기

programmers.co.kr/learn/courses/30/lessons/42883

코딩테스트 연습 - 큰 수 만들기

그리디 + 스택문제이다.

 

문제해결 아이디어 : 앞자리에서부터 세어나가며 내림차순이 되도록 만든다

 

숫자를 스택에 하나씩 쌓아 올려가되 내림차순으로 만든다.

즉 스택을 쌓다가 스택 가장 윗자리 숫자보다 큰 숫자가 나오면 스택을 내림차순이 될 때 까지 pop 해준다.

 

k개를 pop해주었으면 나머지 숫자는 그대로 내비둔다.

 

 

pop한 갯수가 k보다 부족하면 부족한 수 만큼 뒤에서 덜어준다.(내림차순이므로 뒤에 숫자를 빼는게 유리)

 

 

 

def solution(number, k):
    answer = ''
    q = []
    popcnt = 0
    for num in number:
        while q and q[-1] < num:
            if popcnt == k:
                break
            q.pop()
            popcnt += 1
        q.append(num)
    answer = ''.join(q[:len(q) - k + popcnt])
    return answer