파이썬 문제: 4/14

프로그래머스 Level2 : 큰 수 만들기

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

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

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

제한 조건

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

입출력 예

number	k	return
“1924”	2	“94”
“1231234”	3	“3234”
“4177252841”	4	“775841”

해설

이번 문제도 한 5시간은 고민한 것 같다. 레벨 2를 풀면서 부터는 뭔가 개념적인 기초 없이 풀기가 어려워지는 것 같다. 처음에는 앞 문제 풀이와 유사하게 재귀적인 방법을 사용했다. 문자열은 pop이 없으므로 인덱스를 이용해 슬라이싱해서 더해주었고, 매번 한 숫자를 제외할때의 경우의 수는 그 때의 문자열 수만큼 있으므로 그 중에서 가장 큰 값을 구하는 과정을 반복했다.

def solution(number, k):
    number = greedy(number, k)
    return str(number)

def greedy(number, k):
    if k == 0:
        return number
    stack = []
    for idx in range(len(number)): #제외할 수는 그 숫자의 길이만큼 존재
        new_number = number
        new_number = number[:idx]+number[idx+1:] #특정 숫자를 제외
        stack.append(solution(new_number, k-1))
    return max(stack) #제외한 후 결과중 가장 큰 값을 사용

하지만 시간 초과와 런타임 에러가 났다. 모두 불필요하게 많은 중복된 연산때문으로 보인다.

예를들면 1234가 들어왔을때 1을 빼고 2를 빼는 경우나, 2를 빼고 1을 빼는 경우 모두 동일한 결과를 가져오지만 이 동일한 과정이 반복된다.

이를 해결하기위해 다른 방식을 이용해야 했다. 두번째 시도는 모든 경우를 고려하지 말고 첫번째 숫자가 그 다음 숫자보다 작을경우 그 숫자는 제외하는 방식으로, 한 번 제외하고 다시 처음으로 돌아가 다시 탐색하는식으로 반복하면 결국 원하는 가장 큰 값을 구할 수 있다.

def solution(number, k):
    iteration = 0
    while k != iteration: #제외한 수들의 개수가 원하는 수이면 종료
        for idx in range(len(number)-1):
            if number[idx] < number[idx+1]: #앞의 수가 뒤의 수보다 작으면 제외
                number = number[:idx]+number[idx+1:]
                break #한번 제외하면 다시 처음부터 탐색
        else: number = number[:-1] #모든 수가 같을 경우 제일 마지막 수를 제외
        iteration += 1
    return number

이 경우 테스트 10이 시간초과되었다. 숫자가 너무 크다면 number[:idx]+number[idx+1:]가 매번 큰 값이라 계산이 느려지는것 때문으로 보이는데, 파이썬은 문자열의 특정 인덱스를 제거하는 메소드가 없어서 해결 방법이 떠오르지 않았다. 문자열을 리스트로 바꾸고 pop을 사용해 봤는데, 오히려 더 오래걸렸다. 도저히 해결 할 방법이 떠오르지 않아 질문하기를 뒤져보고 다른 방법을 찾았다.

def solution(number, k):
    length = len(number) - k
    min_index = 0
    result = []
    for i in range(length): #만들어야 하는 수의 자릿수만큼 반복
        target_list = number[min_index:k + 1 + i]
        #제일 처음인 [0:k+1]만 생각해 보면 나머지 [k+1:]는 만들어야 하는 수보다 한 자리 적다.
        #따라서 [k+1:]의 모든 수가 9라고 하더라도 앞에서 하나는 뽑아야한다. 이를 이용한다.
        max_value = max(target_list) #하나는 뽑아야 하는 수들의 목록중 최대값을 뽑음
        min_index = target_list.index(max_value) + 1 + min_index
        #하나를 뽑으면 최저 인덱스 기준을 갱신
        result.append(max_value)
    return ''.join(result)

이 방법을 이용하면 테스트 8의 경우 9초에서 2초로 줄일 수 있다. 하지만 여전히 테스트 10에서 시간초과된다. 도저히 모르겠어서 구글링했고, 최적의 방법을 찾았다.

def solution(number, k):
    stack = []
    for idx in range(len(number)):
        stack.append(number[idx]) #모든 수를 우선 stack에 집어넣음
        while k>0 and len(stack)>1 and stack[-1]>stack[-2]:
            #집어넣은 수보다 큰 수가 나올때까지 기존 수들을 뺌
            stack.pop(-2)
            k -= 1
    if k != 0: #모든 과정이 끝났을때 제시된 k보다 적은 수를 제외할 경우
        stack = stack[:-k] #남은 k만큼 추가로 제외
    return ''.join(stack)

갈수록 알고리즘 한 문제를 푸는데 걸리는 시간이 급격히 증가하고 있어서 기본적인 지식을 쌓을만한 자료를 좀 찾아봐야겠다.