[Python] 큰 수 만들기

1. 문제

 

 

 

2. 풀이 과정

방법 1) 시간 초과

number에서 k개를 뺏을 때 len(number) - k 길이의 수를 만들어야 한다.

이 조건에서 첫 번째 자리가 될 수 있는 수는 뒤에서 count 했을 때, 원하는 길이 이상인 값들이 그 후보이다.

 

최댓값과 그의 index값을 따로 찾는 데에 시간이 오래 걸렸다고 판단하였다.

def solution(number, k):
    answer = ''
    pre_idx = -1
    for i in range(1, len(number)-k+1)[::-1]:
        #이전에 선택한 값의 뒤부터 길이에 맞는 곳까지 중 최대값 찾기
        answer += max(number[pre_idx+1:len(number)-i+1])
        pre_idx = number[pre_idx+1:len(number)-i+1].index(answer[-1]) + pre_idx + 1
    return answer

 

방법 2) 가능한 수의 범위 안에서 최댓값을 순차 탐색을 통해 찾는다. 탐색 중 '9'를 만나면 바로 break 해야 더 효율적인 코드가 될 수 있다.

def solution(number, k):
    answer = ''
    pre_idx = -1
    for i in range(1, len(number)-k+1)[::-1]:
        #이전에 선택한 값의 뒤부터 길이에 맞는 곳까지 중 최대값 찾기
        max_v = '-1'
        for j in range(pre_idx+1, len(number)-i+1):
            if max_v < number[j]:
                max_v = number[j]
                pre_idx = j
            #9보다 큰 수는 없으니까 break
            if max_v == '9':
                break
        answer += max_v
    return answer

 

방법 3) stack 사용

원리를 간단하게 말하면, 앞에 있는 수를 제일 크게 만드는 것이다.

수를 처음부터 읽어가면서 현재 읽는 값이 그 전 값보다 크고 k가 0이 아닐 때까지 빼내고 나서, 자신이 stack에 들어간다.

입력값을 한 번 쭉 읽기만 하기 때문에 방법1, 2보다 빠르다.

def solution(number, k):
    answer = ''
    stack = [number[0]]
    
    for n in number[1:]:
        while stack and k > 0:
            if stack[-1] < n:
                stack.pop()
                k -= 1
            else:
                break
        stack.append(n)
        
    return answer.join(stack[:len(stack)-k])