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

1. 문제 설명 및 분석

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

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

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

제한사항

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

number의 범위를 생각했을 때 완전탐색은 제외하고 생각

입출력 예

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

2. 문제 해결

사고 과정

• 결괏갑은 number의 길이 - k 만큼의 길이를 가짐
• 결괏값을 만들기 위한 변수 answer 를 공백으로 초기화한 후
• (1) k - answer의 길이 만큼 number의 숫자를 뒤에서 제외한 후, 가장 큰 값을 선택
• (2) number 앞쪽부터 위에서 추출된 가장 큰 값까지의 숫자를 제외한 후, 다시 위의 범위에서 큰 값을 선택
• answer의 길이가 number의 길이 - k 가 될 때 까지 (1), (2) 를 반복

코드 작성

def solution(number, k):
    answer = ''
    last_idx = 0

    while len(answer) < len(number) - k:
        new_numbers = number[last_idx: k + 1 + len(answer)]  # 이전에 뽑은 숫자의 인덱스부터, 최댓값까지 남은 길이만큼 제거 후 슬라이싱
        max_number = max(new_numbers) # 범위 내에서 최댓값 추출
        last_idx = last_idx + new_numbers.index(max_number) + 1 # 원래의 문자열에서 추출된 값의 인덱스를 찾은 후 할당
        answer += max_number

    return answer

제출 결과

3. 실패 분석 및 문제 해결

실패 분석

• 범위를 지정하고 그 범위내에서 가장 큰 숫자를 찾는 것은 그리디한 방식으로 볼 수 있다.
• while 은 최대 len(number) - k 만큼 반복되고, 이는 O(n-k) = O(n) 의 시간복잡도를 갖는다.
• 그러나 슬라이싱 에서 O(k+1), 인덱스 찾기 에서 O(k+1), 가장 큰 값을 찾기 에서 O(k+1) 총 O(3k+3) = O(k) 만큼의 비효율적인 연산이 진행되므로
• 총시간 복잡도는 O(n*k) 이다. 이는 주어진 인풋에 따라 많은 성능에 차이를 보일 수 있다.
• 슬라이싱, 인덱스 찾기 등의 불필요한 과정을 제외할 방법이 필요하다.
• number 앞부터 숫자를 하나씩 탐색하면서, 이미 탐색된 숫자보다 현재 탐색 중인 숫자가 더 크면 앞쪽의 숫자를 k번 제외하는 방법으로 수정한다.
• 이는 number 의 길이만큼 루프를 돌며, O(n)의 시간 복잡도를 예상할 수 있고, 이미 탐색된 숫자를 비교하고 제거하는 것은 O(k)의 시간 복잡도를 예상한다.
• 총 O(n+k) = O(n) 만큼의 시간 복잡도를 기대할 수 있다.

코드 작성

def solution(number, k):
    stack = []

    for i in number:
        # 만약 현 숫자가 스택에 남은 마지막 숫자보다 클 경우 스택에서 제거
        while k > 0 and stack and stack[-1] < i:
            stack.pop()
            k -= 1
        stack.append(i)
        
    # 제거할 숫자가 더 남았다면 뒤에서부터 제거
    if k > 0:
        stack = stack[:-k]

    return ''.join(stack)

제출 결과

4. 회고

• 범위를 지정하고 가장 큰 수를 남기는 사고는 좋았으나, 이를 코드 옮길 때 범위를 지정하는 것이 비효율적이란 것을 느꼈다. 그런데도 계속 작성을 한 것은 문제가 있다. 충분히 사고하는 과정이 필요할 것 같다.