큰 수 만들기

프로그래머스

 

그리디 문제다.

그리디는 정말... 풀이가 딱 떠오르지 않으면 푸는데 한참 걸리거나 못 푸는 것 같다.

그래서 많이 풀어보는 게 중요하다는 생각이 든다.

 

풀이를 계속 생각해봤지만, 계속 아니더라..

결국 구글링을 참고해서 풀었다.

 

---

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

 

스택을 사용해서 푼다.

 

number를 앞에서부터 확인해서

만약 k > 0이고, stack에 원소가 들어있고, 스택의 최상단 원소가 현재 확인하는 num보다 작다면

stack에 있는 원소를 pop하고 k -= 1을 해준다.

위 과정을 모든 num에 대해 수행했을 때, 만약 k가 아직 남아있다면 뒤에서부터 k개의 숫자를 빼준다.

예를 들면 number가 "4321"이고 k가 2인 경우 반복문을 한번 다 돌아도 "4321" 그대로이므로 뒤에서 숫자 2개를 빼주면 "43"이 나온다.

 

 

꼭 다시 풀어봐야할 문제