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

문제 설명

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

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만

들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

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

제한 조건

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

입출력 예

입출력 예

---

나의 풀이

def solution(number, k):
    answer = ''
    k = len(number) - k
    while k > 0 and len(number) != k:
        for i in range(9, -1, -1):
            if number[:len(number)-k+1].find(str(i)) != -1:
                addNum = str(i)
                break
        answer += addNum
        number = number[number.find(addNum) + 1 :]
        k -= 1
    if len(number) == k:
        answer += number
    return answer

 

아이디어는 다음과 같다

• number의 길이에서 k만큼 빼면 구하고자 하는 숫자의 길이이다. k의 값을 구하고자 하는 숫자의 길이로 저장한다.
• answer에는 구하고자 하는 숫자를 저장할 것이다.

풀이 과정

말로 설명하면 이해하기 힘들 것 같아 만들었다.

number에는 "4177252841" 이 들어있고, k는 4가 입력되었지만, 구할 숫자의 길이인 6으로 변경하였다.

이후 반복문을 돌며 k값을 하나씩 감소시킬 것인데, 

k가 6일때를 보면 앞의 5개 숫자를 묶은 것을 볼 수 있다.

대괄호로 묶은 부분을 하나의 숫자로 본다면 총 6개의 숫자가 된다.

즉, 구해야 할 6개의 숫자 중 가장 첫 번째 숫자가 5번째를 넘어가면 6개의 숫자를 뽑아낼 수 없기 때문에 대괄호로 묶은 부분 내에서 최대 값을 구해야 한다.

최대 값을 구할 때는 max 함수를 사용해도 되지만 대괄호로 묶은 범위가 굉장히 넓을 수 있기 때문에 max()로 돌리면 시간 복잡도가 O(n)이 되어 많은 시간을 소요하게 된다.

이 문제에서는 가장 큰 숫자 하나만 선택하면 되는 것이기 때문에 i를 9 부터 0까지 감소시키며 i가 있는지 확인하는 방법을 선택하였다.

이 방법을 사용함으로써 시간 초과가 나오던 기존의 코드에 비해 굉장히 빠른 코드로 바뀌게 되었다.

그렇게 구한 첫 번째 숫자인 '7'을 answer에 기록한다.

k를 1 감소시키고, 위의 과정을 반복한다. 그림을 보면 훨씬 이해가 쉽다.

---

만약 number의 길이가 k와 같아진다면 number의 숫자 중에서 k개를 뽑아내는 것이므로 전체를 answer에 붙이면 되는 것이다.

그렇기 때문에 while 문의 조건식이 len(number) != k 로 된 것이다. 또한 k와 number의 길이가 같아지지 않고, k가 먼저 0이 된다면 반복문이 멈추지 않고 무한루프에 빠질 것이다. 그렇기 때문에 k가 0보다 클 때를 조건으로 같이 걸어야 한다.

 

기존 코드 (max를 활용) 테스트 결과

# 기존 코드

def solution(number, k):
    answer = ''
    k = l = len(number) - k
    while len(answer) != l:
        if number[:len(number)-k+1].find('9') != -1:
            addNum = '9'
        else: addNum = max(number[:len(number)-k+1])
        answer += addNum
        number = number[number.find(addNum) + 1 :]
        k -= 1
    return answer

이 게시글에서 소개한 코드(9부터 0까지 확인) 의 테스트 결과

테스트 결과

이번에도 알고리즘 복잡도의 중요성을 깨닫는다.