[프로그래머스] 큰 수 만들기 (탐욕법 level 2)

1. 문제

2. 나의 풀이

775284가 답인데 나는 772584가 나온다...

import copy
def solution(number, k):
    candidates = []
    numbers = [int(i) for i in number]
    max_digit = len(number) - k
    print(numbers)
    for idx, i in enumerate(number):
        candidate ='0'
        if len(number[idx:]) > max_digit:
            temp = copy.deepcopy(number[idx:])
            sorted_temp = sorted(temp, reverse=True)
            new_sorted_temp = copy.deepcopy(sorted_temp[:max_digit])
            print(f"temp: {temp}, new_sorted_temp: {new_sorted_temp}", end=" ")
            for t in temp:
                if t in new_sorted_temp:
                    candidate += str(t)
                    new_sorted_temp.remove(t)
            print(f"candidate: {candidate}")
            candidates.append(int(candidate))

    print(candidates)
    return max(candidates)

number, k = "4177252841", 4
print(solution(number, k))

3. 남의 풀이

• https://scarletbreeze.github.io/articles/2019-07/pythonKit%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4(4)%ED%83%90%EC%9A%95%EB%B2%95%ED%81%B0%EC%88%98
  
• 남의 코드 분석

def solution(number, k):
    colllected = []

    for i, num in enumerate(number):
        print(f"for문의 시작>>> i: {i}, collected: {colllected}, num: {num}, k: {k}")

        # 아래의 while문은 참 greedy하다
        while len(colllected) > 0 and colllected[-1] < num and k > 0:
            print(f"     start while(collected의 마지막은 num({num})보다 커야햅: >>> i: {i}, collected: {colllected}, num: {num}, k: {k}")
            colllected.pop()
            # while(collected의 마지막 num({num})보다이 작을 때마다 k는 작아저요
            k -= 1
            print(f"     fnish while>>> i: {i}, collected: {colllected}, num: {num}, k: {k}")
            print(f"     ----------------------------------------")

        # k는 최대 collected에서 팝하는 제한
        # 앞의 자리수일 수록 큰 숫자여야하니깐 처음부터 큰 것만 골라내는 것임!
        if k == 0:
            colllected += list(number[i:])
            print(f"for문의 마지막(k==0인 순간)>> i: {i}, collected: {colllected}, num: {num}, k: {k}")
            break

        # collected에 숫자를 하나씩 넣어 줌
        print(f"num({num})을 collect에 넣어주어요")
        colllected.append(num)
        print(f"for문의 마지막>> i: {i}, collected: {colllected}, num: {num}, k: {k}")
        print("="*50)

    print(">>>>>>>>>>for문 종료>>>>>>>>>>>>")
    print(f"for문 종료 후>> i: {i}, collected: {colllected}, num: {num}, k: {k}")
    colllected = colllected[:-k] if k > 0 else colllected
    answer = ''.join(colllected)
    return answer


number, k = "12345123", 3
# number, k = "987654321", 4
print(solution(number, k))

/usr/local/bin/python3.7 /Users/marie/PycharmProjects/monday_1010/training_uniform.py
for문의 시작>>> i: 0, collected: [], num: 1, k: 3
num(1)을 collect에 넣어주어요
for문의 마지막>> i: 0, collected: ['1'], num: 1, k: 3
==================================================
for문의 시작>>> i: 1, collected: ['1'], num: 2, k: 3
     start while(collected의 마지막은 num(2)보다 커야햅: >>> i: 1, collected: ['1'], num: 2, k: 3
     fnish while>>> i: 1, collected: [], num: 2, k: 2
     ----------------------------------------
num(2)을 collect에 넣어주어요
for문의 마지막>> i: 1, collected: ['2'], num: 2, k: 2
==================================================
for문의 시작>>> i: 2, collected: ['2'], num: 3, k: 2
     start while(collected의 마지막은 num(3)보다 커야햅: >>> i: 2, collected: ['2'], num: 3, k: 2
     fnish while>>> i: 2, collected: [], num: 3, k: 1
     ----------------------------------------
num(3)을 collect에 넣어주어요
for문의 마지막>> i: 2, collected: ['3'], num: 3, k: 1
==================================================
for문의 시작>>> i: 3, collected: ['3'], num: 4, k: 1
     start while(collected의 마지막은 num(4)보다 커야햅: >>> i: 3, collected: ['3'], num: 4, k: 1
     fnish while>>> i: 3, collected: [], num: 4, k: 0
     ----------------------------------------
for문의 마지막(k==0인 순간)>> i: 3, collected: ['4', '5', '1', '2', '3'], num: 4, k: 0
>>>>>>>>>>for문 종료>>>>>>>>>>>>
for문 종료 후>> i: 3, collected: ['4', '5', '1', '2', '3'], num: 4, k: 0
45123

Process finished with exit code 0