[programmers] Greedy - 큰 수 만들기

문제

programmers.co.kr/learn/courses/30/lessons/42883

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

 

풀이

조건을 간단하게 정리해 보면, 전체 숫자에서 몇 개의 숫자를 빼서 가장 큰 숫자를 만드는 게 관건이다. 그래서 필자는 우선 전체에서 숫자를 빼내는 것보다는, 전체 중 숫자들을 골라내서 가져오는 것이 알고리즘 구상에 더 용이하다고 판단하였다.

그래서 처음에 choose라는 전체 길이에서 k값만큼을 뺀, 선택해야 하는 숫자의 개수를 이용하였고, choose가 0이 되면 빠져나올 수 있도록 알고리즘을 작성하였다.

이후 반복 과정에서의 아이디어는, 뒤쪽 숫자를 모두 선택한다고 가정했을 때, 앞쪽에서 가장 큰 숫자를 고를 때가 가장 큰 값이 된다는 점이다. 이후 앞쪽에서 숫자를 고르면, 그 숫자 이후로 다시 반복을 진행하면 된다. 그러다가 고른 숫자가 앞쪽에서 맨 뒤 숫자일 경우, 그 이후의 숫자들을 모두 선택한다고 판단하면 된다. 또한 시간을 줄이기 위해, 큰 값을 선택할 때 숫자가 9가 나오는 경우에는 그 뒤쪽을 확인할 필요가 없기 때문에 바로 넘어가는 방식으로 시간을 줄여 주었다.

처음에는 pop 연산을 이용하여 프로그램을 진행했는데, pop 연산 자체가 O(n)의 시간 복잡도를 갖기 때문에, 시간 초과가 자주 일어났다. 그래서 이 시간 초과를 해결하기 위해 startidx와 endidx를 통해 투포인터 알고리즘을 적용하였다. 반복을 idx를 이용해 주고, 앞쪽 값들의 시작점과 끝점을 각각 포인팅하여 문자열의 슬라이싱 없이도 순환할 수 있도록 적용하였다.

해당 알고리즘 문제에서는 알고리즘 구상 단계에서 k를 이용해서 단순히 빼내는 것이 아니라 유효한 숫자들을 골라내는 방식으로 반대로 생각하는 것, 시간 관련해서는 pop을 사용하지 않고 투포인터를 사용하여 시간을 줄이는 것, 그리고 9가 나오는 경우 뒤쪽을 확인할 필요 없이 바로 넘어간느 방식으로 시간을 줄이는 것이 주요했다.

 

코드

def solution(number, k):
    answer = ''
    startidx = 0
    endidx = 0
    choose = len(number) - k
    
    while True:
        idx = -1
        endidx = len(number)-1 - (choose-1)
        
        if endidx < startidx or choose == 0:
            break
            
        elif startidx == endidx:
            answer += number[startidx:]
            break
            
        maxval = -1
        
        for i in number[startidx:endidx+1]:
            if maxval < int(i):
                maxval = int(i)
                
            if maxval == 9:
                break
                
        idx = number[startidx:endidx+1].find(str(maxval))
        answer += str(maxval)
        startidx += idx+1
        choose -= 1
        
    return answer