큰 수 만들기 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의 자릿수 미만인 자연수입니다

문제 원리파악

처음에는 문제를 잘못 이해해서 permutations 써서 최대값 하면 되는 문제인줄 오해했다. 전혀 그런 문제가 아니였는데.

일단 문제는 number의 숫자 리스트의 위치를 바꾸는 것이 아니라 현재 위치에서 숫자를 제거했을 때, 최대값을 구하는 문제였다.

찾은 조건

 

1) 제거가 불가능 할 때까지, 앞의 자릿수가 가장 큰것을 그리디하게 가져갈것  

 

2) 인덱스 다음에 위치한 값이 클 때, 앞에 추가된 값은 모두 제거됨

단, 제거될 때마다 K값도 1씩 줄어듬

 

3) K가 0이되면 나머지 number를 모두 반환

풀이해석

def solution(number, k):
    answer = ''
    
    num_list = []
    
    for val in number:
        # 맨 처음 비교할 대상을 만들어 주기 위해 리스트 값이 없을 때 맨처음 값을 넣어준다.
        if len(num_list) == 0:
            num_list.append(val)
            continue
        
        # 리스트 맨 뒤에 값이 number순서의 값보다 클때만 반복
        # 이러면 K번 제거하는 만큼 앞에 값이 큰 값으로 그리디하게 가져갈 수 있음
        while num_list[-1] < val:
            if k > 0:
                k = k - 1
                num_list.pop()
            
            # K값이 0보다 작으면 더이상 제거할 기회가 없음
            # 또한, 앞에 값들을 다 제거했을 때 조건문을 탈출
            if k <= 0 or len(num_list) == 0:
                break
                
        num_list.append(val)
    
    answer = ''
    
    # 이렇게 결과를 출력하면 마지막 테스트가 틀리더라
    for a in num_list:
        answer += a

    return answer

solution("4177252841", 8)

아래처럼 리스트 값을 묶어서 return하니 값이 테스트값중 하나가 틀리더라

확인해보니 인덱스의 다음 값이 클때 조건이 발동하는데 작은 값으로 계속해서 리스트에 들어가게 되니 그대로 출력한 것

solution("4177252841", 8)  8개를 제거했는데 출력값이 84가 나와야 하는데 841이 나옴

따라서, 전체길이에서 뺀값만큼 출력하도록 하면 문제가 없다

    for a in num_list:
        answer += a
    
    return answer[:len(num_list) - k]

 

깨달은 점

일단..문제를 잘 읽어고 이해하는게 먼저인거같다. 짧은 문제라 좋아했는데 막상 이해하고 보니 마냥 단순한 방식은 아니였다..

앞으로 시간을 아끼고 문제를 많이 접하기 위해

문제를 읽고 2시간 정도 걸리면 -> 다른사람 풀이 해석을 보고(코드가 아님) 적용 -> 그래도 안되면 코드를 보고 풀이

문제를 이해하고 다른사람 풀이의 도움을 받아 풀게되면 문제 초기화해서 구글링없이 블로그에 정리하면서 풀면서 정리하자.