[프로그래머스] 탐욕법 (Greedy) - 큰 수 만들기 (Python)

👻 문제

• 문제 설명
  어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

  예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

  문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

• 제한 조건
  number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
  k는 1 이상 number의 자릿수 미만인 자연수입니다.

• 입출력 예
  

👩‍💻 My cording

풀이 1 : ''.join(), for문 활용

# 가장 큰 숫자
# 가장 작은 수들을 뺀다.
def solution(number, k):
    answer = ''
    num = list(map(int, number))
    #문자열을 하나씩 쪼개서, list에 int로 추가
    #[1, 9, 2, 4]
    for _ in range(k):
        num.remove(min(num))
   
    answer = ''.join(map(str, num)) #리스트를 다시 합쳐서 문자열 변환
    return answer
           
    #111991
    #제일 큰 수가 맨 앞에 가는 것이 유리한데...
    #그렇게 생각하면 4번째 예시랑 맞지 않음

---

• 🐱‍👤 주어진 입출력 예는 출력했지만, 시간초과 + 실패
  

풀이 2

풀이 출처

def solution(number, k):
    answer = []
    for num in number:
        # answer에 뭐라도 존재하고, k가 0보다 크며, answer의 맨 위 값이 현재의 num보다 작으면
        while answer and k > 0 and answer[-1] < num:
            # answer의 맨 위 값을 제거하고 k -= 1
            answer.pop()
            k -= 1 
        answer.append(num)
   
    # answer는 number의 길이 - k만큼 슬라이싱 해준다.
    # -> 슬라이싱은 index 바깥으로 나가도 괜찮음! 
    # 일반적으로 k는 0일텐데 ex) k = 3 number = 1000000 이런 경우엔 k는 처음 인풋받은 그대로 유지됨
    # 이럴 때 답은 뒷 숫자를 k개만큼 없애준 1000 이므로 슬라이싱을 len(number) - k로 해주는 것
    answer = ''.join(answer[:len(number)-k])
   
    return answer

문제출처 : 프로그래머스