[프로그래머스] 큰 수 만들기 (Level 2)

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

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

[프로그래머스] 큰 수 만들기 (Level 2)

그리디 문제

 

number string에서 k개의 숫자를 제거했을 때 가장 큰 수를 만드는 문제

 

 

k가 남아있다면, 자신보다 작은 앞의 숫자는 모두 지워준다.

k가 남아있지 않다면, 남은 숫자를 다 붙여주고

-number : "1231234"

-k : 3

-answer : "3234"

stack	[ ]	['1']	['2']	['3']	['3','1']	['3','2']	['3','2','3','4']
k	3	3	2	1	1	0

 

모든 숫자를 다 탐색했지만, k가 남아 있을 경우, 뒤에서 k만큼 숫자를 잘라준다.

-number : "9999"

-k : 2

-answer : "99"

stack	[ ]	['9']	['9','9']	['9','9','9']	['9','9','9','9']
k	2	2	2	2	2

''.join(stack[:-k]) if k>0

''.join(stack[:len(stack)-k])

 

<파이썬 코드>

def solution(number, k):
    s = []
    for n in number:
        while s and k > 0 and s[-1] < n:
            s.pop()
            k -= 1
        s.append(n)
    print(s[:k])
    return ''.join(s[:len(s) - k])