[python] 프로그래머스 탐욕법(Greedy) 큰 수 만들기

📋 문제

큰 수 만들기
문제 설명
어떤 숫자에서 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"
출처

🐍 이전 풀이(2021.06.22)

from collections import deque

def solution(number, k):
    number = deque(number)
    length = len(number)
    stack = []
    
    while len(number) > 0:
        if k == 0: break
        
        if len(stack) == 0:
            stack.append(number.popleft())
        else:
            if stack[-1] < number[0]:
                stack.pop()
                k -= 1
            else:
                stack.append(number.popleft())
    
    stack = list(stack) + list(number)
    return "".join(stack[:length - k])

🐍 python 풀이

빼야하는 수의 개수가 정해져 있으니 결과값이 가장 큰 수가 되려면 뺄 수 있는 값 중에서 가장 작은 수를 빼야한다. 근데 마지막 예제 "4177252841" 를 보면 결과값이 "775841" 이다. 가장 작은 수를 뺐다면 일의 자리 1이 없었어야 한다. 결국 이 문제는 가장 작은 수만을 찾아 제외하는 것이 아닌 높은 자리에 있는 값이 커야한다.
"4177252841"은 4개의 숫자를 제외하므로 결과값이 총 6자리의 수이다. 결과값이 나올 수 있는 범위가 000,000에서 999,999까지인 것이다. 주어진 수에서 십만 자리의 수가 가장 크려면 결국 앞에서부터 확인하여 현재 상황에서 작은 수를 제외하는 것이고 이것은 그리디 문제가 된다.
문제에서 number의 수는 1이상이라고 했으므로 10000000이 나올 수도 있다. 값을 생각 안하고 제외한다면 000000이 결과로도 나올 수는 있다.

"4177252841"로 봤을 때,
1. 4는 첫번째 수이므로 일단 결과값에 추가한다.
2. 1은 추가된 가장 마지막 수인 4보다 작으므로 추가한다.
3. 7은 추가된 가장 마지막 수인 1보다 크므로 1을 삭제한다. (k=1)
4. 7은 추가된 가장 마지막 수인 4보다 크므로 4를 삭제한다. (k=2)
5. 더이상 7보다 큰 수가 없으므로 추가한다.
6. 7은 추가된 가장 마지막 수인 7과 같으므로 추가한다.
7. 2는 추가된 가장 마지막 수인 7보다 작으므로 추가한다.
8. 5는 추가된 가장 마지막 수인 2보다 크므로 2를 삭제한다. (k=3)
9. 2는 추가된 가장 마지막 수인 5보다 작으므로 추가한다.
10. 8은 추가된 가장 마지막 수인 2보다 크므로 2를 삭제한다. (k=4)
k가 주어진 수만큼 채워졌을때까지 추가한 수들은 모두 내림차순 정렬이다. 더이상 수를 제외할 수 없으므로 남은 수는 붙여서 결과로 출력한다.

def solution(number, k):
    answer = []
    count = 0
    index = 0
    
    for i, num in enumerate(number):
        index = i
        # 비어있을 경우 채워넣기
        if not answer:
            answer.append(num)
            continue
        
        # 값이 존재할 경우 값 크기 비교
        while answer:
            if answer[-1] < num:
                answer.pop(-1)
                count += 1
                if k == count:
                    break
                continue
            break
        answer.append(num)
        
        if k == count:
            break
    
    # 나머지 숫자 모두 붙이기
    answer.append(number[index + 1:])
    
    return "".join(answer[:len(number) - k])

실행속도 개선

1. list.pop(-1) -> list.pop()

answer.pop(-1)

16번째 줄에 있는 코드를

answer.pop()

다음과 같이 수정하였다.

python의 list는 pop(n)연산을 수행한 후 빈 공백을 기준으로 나머지 요소들을 한 칸씩 앞당긴다. 그에 반해 pop()은 가장 마지막 요소를 제외하기 때문에 앞당길 필요가 없다. pop(n)은 시간복잡도가 O(n)이며 pop()은 O(1)인 이유이다.
pop(-1)도 어차피 가장 마지막 요소를 제외하는 것이므로 시간 차이가 없을 거라 생각했는데 실행시간이 줄어들었다. 현재 제외한 요소가 몇번째 요소인지 판단하는 과정이 포함되어 시간이 더 소요되었다고 추측한다.

테스트 케이스 8, 10 실행시간이 줄어들었다.

🐍 다른 사람 풀이

• 주어진 k를 사용하여 카운트하여 변수를 쓸데없이 할당하지 않았다.
• stack의 가장 윗 숫자(list의 마지막 숫자)보다 현재 입력해야 하는 값이 더 크고 뺄 수 있는 수(k)가 0이 아닌 조건이 모두 만족해야 하므로 한줄에 해결하여 코드의 수를 줄였다.

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