[프로그래머스] 큰 수 만들기 풀이

1. 문제

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

2. 풀이

2.1. 시간 초과 풀이

만들어야 하는 자리 수는 number의 길이 - 빼야할 숫자 k 입니다.
숫자를 결정할 때 가장 높은 자리 숫자부터 정해야 합니다.
- 높은 자리 숫자는 현재 string 에서 최소한 빼야할 숫자 k - 1개 만큼이 뒤에 포함되어 있어야 합니다.
- 예를 들어, ‘2223454’ 에서 4개의 숫자를 빼야 되면 자리 수는 3자리이고, 첫 숫자는 뒤에 최소한 4 - 1 = 3개 만큼의 숫자 ‘454’ 앞에 있어야 하기 때문에 ‘2223’ 중에 하나입니다.
위와 같이 반드시 살펴봐야 하는 구간 중에서 가장 큰 수를 취하는 과정을 반복적으로 수행하면 답을 얻을 수 있습니다.
하지만 이 문제는 8, 10번 케이스에서 시간 초과가 굉장히 많이 발생합니다.

def solution(number, k):
    answer = ""
    need_word_length = len(number) - k
    left = 0
    while need_word_length:
        see_max_idx = left
        for right in range(left + 1, len(number) - need_word_length + 1):
            if number[see_max_idx] < number[right]:
                see_max_idx = right 

        answer += number[see_max_idx]
        need_word_length -= 1
        left = see_max_idx + 1

    return answer

2.2. 시간 줄이는 팁

시간을 줄이기 위하여 매우 많은 시도들을 하여 겨우 통과했습니다.
number string을 string으로 비교하고 int로 비교하지 않는 경우에 속도가 훨씬 더 빨랐습니다. 하지만 문제 해결에는 큰 도움이 되지 않습니다.
핵심 문제 해결방법은 아래와 같습니다.
- for 문에 들어가기 전에 if 문을 통하여 ‘9’인지 확인합니다. 9는 최대 숫자이기 때문에 확인하는 즉시 정답 배열에 넣습니다.
- 아래 코드의 핵심 시간 단축 포인트 1과 2가 모두 포함되어있어야 합니다.

def solution(number, k):
    answer = ""
    need_word_length = len(number) - k
    left = 0
    while need_word_length:
        see_max_idx = left
        if number[see_max_idx] !=  '9':  ## 핵심 시간 단축 포인트 1
            for right in range(left + 1, len(number) - need_word_length + 1):
                if number[see_max_idx] < number[right]:
                    see_max_idx = right 
                    if number[right] == '9':  ## 핵심 시간 단축 포인트 2
                        break

        answer += number[see_max_idx]
        need_word_length -= 1
        left = see_max_idx + 1

    return answer

PREVIOUS[프로그래머스] 피보나치 수 풀이

NEXT[프로그래머스] 위장 풀이