[프로그래머스/Python] LV2. 큰 수 만들기 (+7)

프로그래머스 코딩테스트 연습 - LV2. 큰 수 만들기

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

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

 

문제 설명

어떤 숫자에서 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"

 

풀이 방법

❌ 시간 초과 코드 1 : combinations로 가능한 전체 조합 인덱스 추출 후, 최대값 찾기 (탐욕법 X)

from itertools import combinations as cb

def solution(number, k):
    number = list(number)
    idxs = list(map(list, list(cb(range(len(number)), len(number)-k))))
    nums = []
    for idx in idxs:
        n = []
        for i in idx:
            n.append(number[i])
        nums.append("".join(n))
    return max(nums)

• 테스트 3, 4, 5, 6, 7, 8, 9, 10 - 실패 (시간초과)
• combinations로 인덱스 조합 추출하고, 해당 인덱스들로 구성된 숫자 리스트 추출하고, 그 중에서 max 값을 구하니 성능 쓰레기,,

 

❌ 시간 초과 코드 2 : 숫자 하나씩 빼보며 최대값 찾기를 k번 반복

def solution(number, k):
    for i in range(k):
        max_num = number[1:]
        for i in range(1, len(number)):
            new_num = number[:i] + number[i+1:]
            if new_num > max_num:
                max_num = new_num
        number = max_num
    return max_num

• 테스트 6, 7, 8, 9, 10 - 실패 (시간 초과)
• O(len(number) * k)

 

❌ 시간 초과 코드 3 : number[:-k]의 문자열부터 시작하여 어떤 숫자를 빼고, 다음 숫자를 넣을 지 여부를 이중 for문으로 비교 탐색

def solution(number, k):
    _max = number[:-k]
    for i in number[-k:]:
        for j in range(len(_max)):
            _new = _max[:j]+_max[j+1:]+i
            if _new > _max:
                _max = _new
                break
    return _max

• 테스트 7, 8, 10 - 실패 (시간 초과)

 

✨ 성공 : num 리스트를 하나 만들어서 number의 숫자들을 하나씩 넣어갈 때, num에 보다 작은 숫자가 있으면 빼는 것을 k번 반복, 작은 숫자가 없으면 넣기만!

def solution(number, k):
    num = [number[0]]
    for i in range(1, len(number)):
        if k < 1:
            num.append(number[i:])
            break
        while len(num) > 0 and k > 0 and number[i] > num[len(num)-1]:
            num.pop()
            k -= 1
        num.append(number[i])
    if k != 0:
        num = num[:-k]
    return "".join(num)

• num.pop()을 num = num[:-1]로 썼었다가 "테스트 10 - 실패 (시간 초과)"의 결과를 받았었다. 🥲

 

🔺 보류(조금만 고치면 될 것 같음) : 첫번째 자릿수로 가능한 범위의 숫자들 중 가장 큰 수를 뽑고, 뽑힌 수의 다음 인덱스부터로 탐색 scope를 줄여 다음 자릿수를 탐색하는 방식

def solution(number, k):
    num = []
    i = -1
    while k < len(number):
        i += 1
        scope = number[i:k+1]
        max_num = max(scope)
        num.append(max_num)
        i += scope.index(max_num)
        k += 1
    return "".join(num)

• 테스트 10 - 실패 (시간 초과)

 

느낀 점

59번째로 푼 문제였는데 가장 많은 방법으로 시도해본 것 같다.(포스팅의 이유)

결론은 알고리즘이 맞아도 코드를 거지같이 짜면 시간 초과가 뜰 수 있다는 것을 뼈저리게 느낌

 

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges