프로그래머스 코딩테스트 고득점 Kit_탐욕법(Greedy)_큰 수 만들기

문제 보러 가기 👈 클릭!

💡 풀이

✔ 풀이 방법

• stack자료구조 사용
• number를 반복하며 stack에 값을 추가한다.
  단, 현재값이 stack[-1] 값보다 클 경우 현재값 이상의 값이 나올 때 까지 stack의 값을 제거한다. (k번 이하 제거)

구현 코드 1👇

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

구현 코드 2👇

number를 다 반복하는 중간에 k개의 수를 제거했다면 바로 반복문을 종료하며 return하는 조건을 추가함

def solution(number, k):
    stack = []
    for i, num in enumerate(number):
        if not k:
            stack.extend(number[i:])
            return ''.join(stack)
        
        while stack and k and num > stack[-1]:
            stack.pop()
            k -= 1
        stack.append(num)
        
    return ''.join(stack[:len(stack) - k])

=> 코드는 늘어났지만, 더 빠르다.