[프로그래머스 LV.2] 큰수 만들기 (feat. python 그리디 풀이)

 

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

 

 

알고리즘 고득점 kit에 있는 것이라서 카테고리 유형이 greedy인걸 인지 해버린채(?)풀었다.

가장 큰 수? 이런거 나오니까 그리디라고 생각하면 좋을 것 같다.

 

생각한 시간에 비해 코드는 간단했다. 

처음에는 순열 조합 이런걸로 푸는건가 싶었는데 시간 초과가 날것 같았다. 

그래서 stack을 활용해 그리디 문제 풀듯이 풀었다. 

 

 

 

문제 요약

숫자 문자열 number에서 k개 숫자를 제거해서,
남은 숫자들의 순서를 유지하면서
만들 수 있는 가장 큰 수를 return하는 것이다.

def solution(number, k):
    #스택 풀이 
    stack=[]
    for i in number:
        while stack and k>0 and stack[-1]<i:#스택이 있고, 들어있는 수가 들어온 수보다 작으면 pop
            stack.pop()
            k-=1
        stack.append(i)
        
    if k>0:
        stack=stack[:-k]
    return ''.join(stack)

 

문제 풀이 

 

하나씩 보면서 스택에 쌓되, 현재 숫자가 스택의 마지막 숫자보다 크면 pop (그리고 k -= 1)

 

while 문 안에서 "뒤에 더 큰 숫자가 나타날 때 앞의 작은 숫자를 제거"하는 작업을 한다.

만약 그런 상황이 오지 않으면?

→ k만큼 숫자를 다 못 없앰.
→ 그래서 남은 k만큼 뒤에서 숫자를 자른다.

 

남은 k는 뒤에서 제거함. 

이미 숫자를 다 봤는데도 k가 0이 아니면, 스택 뒤에서 k개를 잘라내기

 

if k>0:조건을 달아주었으니까 k = 0일 때는 건드리지 않을 수 있다.