[프로그래머스] 그리디 - 큰 수 만들기, 파이썬

문제

---

• 문제 링크
• number 문자열이 주어지고 자연수 k가 주어질 때 k 개의 문자를 제거한 가장 큰 수를 문자열로 리턴해야 하는 문제이다.

풀이

---

• 레벨 2
• 스택, 문자열 처리
• 어려운 편은 아니지만 시간초과가 나올 수 있으며 테스트케이스 12번이 틀릴 수 있다.(Part 2 참조)

  Part 1

• 우선 문자열을 arr 배열에 담아준다.
• 반복문을 돌며 만약 stack이 비어있지 않고 stack의 마지막 원소가 지금 문자열의 수보다 작으면 while문으로 들어간다.
• 이때 k가 0보다 크고(제거할 문자열이 있고) stack에 문자열이 있고 stack의 마지막 원소가 지금 문자열보다 작으면 stack의 마지막 원소를 제거해준다.
• 이렇게 할 때 k가 0보다 클 때 stack은 내림차순으로 정렬된다.
• 큰 수를 위해서는 높은자리수(앞쪽의 문자열)이 큰 수여야 하기 때문데 k가 0보다 클 때 내림차순 정렬을 유지하는 것이다.

  Part 2

• 반복문이 끝났는데 k가 0보다 클 때는 내림차순 정렬이라는 뜻이기 때문에 stack의 마지막 원소를 k만큼 제거해준다.

코드

---

def solution(number, k):
    # Part 1
    arr = [s for s in number]
    stack = []
    for i in range(len(arr)) :
        if stack and stack[-1] < arr[i] :
            while stack and stack[-1] < arr[i] and k > 0 :
                stack.pop()
                k -= 1
        stack.append(arr[i])
    ###
    # Part 2
    while k > 0 :
        stack.pop()
        k -= 1
    return str(''.join(stack))
    ###