탐욕법 - 큰 수 만들기

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

---

방법

• 앞 자리에서부터 하나씩 골라서 담되,
  • 지금 담으려는 것보다 작은 것들은 도로 뺀다!
  • 단, 뺄 수 있는 수효에 도달할 때까지만
• 큰 수가 앞자리에, 작은 수가 뒷자리에 놓이도록
  • (제약조건) 뺄 수 있는 수의 개수

알고리즘 설계 -> 구현

• 주어진 숫자(number) 로부터 하나씩 꺼내어 모으되
  • 이 때, 이미 모아둔 것 중 지금 등장한 것보다 작은 것들을 빼낸다.
  • 이것은 어디서 어떻게 살펴보아야?
• 이렇게 모은 숫자들을 자릿수 맞추어 변환한다.
  • 아직 뺄 개수(k) 를 채우지 못한 경우
  • 자릿수는 어떻게 계산하는가?
•  

def solution(number, k):
    collected = [] # 여기에 숫자를 한자리씩 채움
    for i, num in enumerate(number):
        while len(collected) > 0 and collected[-1] < num and k > 0:
            collected.pop()
            k -= 1
        if k == 0:
            collected += list(number[i:])
            break
        collected.append(num)
    # 만약 98765 인 경우면 위 로직에서는 뒤의 넘버가 현제의 넘버보다 클 경우에만 k를 줄이고 수를 빼주기 때문에 아무것도 남지 않을것 따라서 collected가
    # number 리스트와 똑같이 생겻을 것 그 경우를 예외 처리 해주는 코드
    collected = collected[:-k] if k > 0 else collected
    return ''.join(collected)