[Programmers] 큰 수 만들기 (Python)

코딩테스트 연습 - 큰 수 만들기

 

오랫동안 못 풀었던 큰 수 만들기 문제!

오랜만에 도전했더니 생각보단(?) 금방 해결해서 기분이 좋다!

 

그리디 = 매 순간 최선의 선택을 하는 문제! 라는 것에 집중하면 문제 해결방법을 금방 생각해낼 수 있다.

 

가장 큰 수를 만들기 위해서 매 순간 할 수 있는 가장 최선의 선택은 무엇일까?

큰 수의 조건은 무엇인가!?

 

일단 큰 수가 되려면 무조건 맨 앞자리 숫자가 가장 커야한다.

따라서 앞에서부터 비교했을 때 

현재 자릿수 숫자 < 다음 자릿 수 숫자 이면

현재 자릿수의 숫자를 제거하는 것이 바람직하다는 것!

 

또한 제거하고나서 매번 처음부터 다시 비교하면 시간초과가 나므로

제거한 숫자 전 바로 이전 자릿수부터 다시 비교해야한다.

이전 자릿수부터 비교해야 하는 이유는

517 -> 1제거 -> 57 -> 5제거 -> 7

이런 식으로 하나를 제거하면서 이전 자릿수를 다시 제거해야하는 케이스가 있을 수 있기 때문이다!

 

또한 한 바퀴 다 돌았는데 더 이상 제거할 숫자가 없다는 뜻은

999999와 같이 모든 자릿수의 숫자가 동일하다거나

9876543과 같이 앞에서 제거할 숫자가 없다는 뜻이다.

 

따라서 이런 케이스에서는 마지막 자릿 수를 남은 제거해야할 숫자만큼 제외해주면된다!

 

 

def solution(number, k):
    remove_idx = 0
    while k > 0 :
        idx1 = max(0, remove_idx)
        for idx2 in range(idx1+1, len(number)) : # 비교할 인덱스
            if int(number[idx1]) < int(number[idx2]) :
                number = number[:idx1] + number[idx2:]
                remove_idx = idx1-1
                break
            idx1 = idx2
        else : 
            return number[:len(number)-k]
        k -= 1
    return number