프로그래머스 level2 - 큰 수 만들기

문제

어떤 숫자에서 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	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

slice와 max를 이용해서 풀면 된다고 생각하고 아래와 같이 짜보았다.

def solution(number, k):    
    answer = ''
    remain = len(number) - k  # 최종 숫자의 길이

    while remain > 0:
        # 탐색할 범위: 현재 남은 숫자 길이에 따라 조정
        slice_len = len(number) - (remain - 1)
        # 가장 큰 숫자 선택
        max_num = max(number[:slice_len])
        answer += max_num
        # 선택한 숫자 이후의 문자열로 이동
        number = number[number.index(max_num) + 1:]
        remain -= 1

    return answer

문제를 해결한 줄 알았는데 테스트 10번에서 시간 초과가 떴다.. 

위의 코드는 아래와 같은 문제점이 있다

 

1. 부분 문자열 탐색 (최대값 찾기):

• max(number[:slice_len]은 슬라이싱된 문자열의 최대값을 찾는다
• 슬라이싱과 최대값 찾기는 각각 O(slice_len)에 해당된다.

2. 문자열 이동:

• number = number[number.index(max_num) + 1:]는 선택된 숫자 이후의 문자열로 이동한다.
• 문자열을 복사하므로 O(n)의 복잡도를 가진다.

3. 최악의 경우 복잡도 계산

• number의 길이를 n, 최종 선택할 숫자의 길이를 r(r = n - k)
• 각 단계에서 슬라이싱 및 최대값 탐색을 수행하면 n, n-1, n-2, ...., n-r+1 크기의 부분 문자열을 탐색한다
• 따라서 총 시간 복잡도는
  O(n+(n−1)+(n−2)+⋯+(n−r+1))=O(2(2n−r+1)r​)≈O(n2) 

4. 효율성이 떨어지는 이유

• 슬라이싱과 복사
  • Python에서 문자열은 불변 객체이므로 슬라이싱이나 문자열 이동은 새로운 문자열을 생성하기 때문에
    문자열의 길이가 길어질수록 메모리 사용량이 증가한다.
• 최대값 탐색
  • max()가 반복적으로 호출된다. 각각의 호출은 탐색 범위에 비례하여 시간이 걸린다
• 중복 작업
  • number를 탐색하고 나서 선택된 문자를 기준으로 다시 이동하는 작업이 반복적으로 발생한다.

해결 방안

스택 기반 탐욕 알고리즘을 사용하여 효율성을 개선할 수 있다. 스택 기반 접근법은 모든 숫자를 한 번만 탐색하면서 O(n) 시간복잡도로 결과를 도출한다. 

 

def solution(number, k):
    stack = []
    for num in number:
        # 현재 숫자가 스택의 마지막 숫자보다 크면 제거
        while stack and k > 0 and stack[-1] < num:
            stack.pop()
            k -= 1
        stack.append(num)
    # 남아있는 숫자만큼 결과 생성
    return ''.join(stack[:len(stack)-k])

 

위의 코드와 같이 조건에 부합하면 stack에 담겨있는 요소를 제거(pop)하고 그 외의 경우에는 stack에 요소를 추가(append)한다.