💡 문제

큰 수 만들기

• 유형 탐욕법(Greedy)

• 문제 설명 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

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

• 입력
  • ex1) "1924", 2
  • ex2) "1231234", 3
  • ex3) "4177252841", 4

• 출력
  • ex1) "94"
  • ex2) "3234"
  • ex3) "775841"

• 참고
  • Programmers | 큰 수 만들기 - Python
  • [Python] - 그리디 알고리즘(Greedy Algorithm) 개념
  • [알고리즘]그리디(Greedy, 탐욕법, 욕심쟁이기법)

✍🏻 풀이

TRY 1

# TRY 1)

from itertools import combinations

def solution(number, k):
    number = list(number)
    order = list(combinations(range(len(number)), len(number)-k)) # 1️⃣
    print(order)
    nums = []
    for i in order:
        nums.append(''.join([number[j] for j in i]))
    return max(nums)

처음엔 조합을 이용해서 number에서 k개의 수를 제거해서 나올 수 있는 모든 경우의 수를 구해서 그 중 최댓값을 뽑는 방식이 직관적으로 떠올라서 가장 먼저 구현해 보았다. 역시나는 역시나 였다. '생각보다 너무 간단하게 구현되는 것이 아닌가?' 했더니 역시나 시간 초과라는 메시지를 통해 오만하지 말고 인간의 사고가 아닌 컴퓨터의 언어로 문제를 해결하라는 교훈을 다시 한 번 되새길 수 있었다.

1️⃣을 print하면 아래와 같이 number에서 len(number)-k개 만큼 뽑을 때 인덱스의 가능한 경우의 수 리스트를 확인할 수 있다.

TRY 2

# TRY 2)

from itertools import combinations

def solution(number, k):
    result = '0'
    for i in combinations(range(len(number)), len(number)-k):
        temp = ''.join([number[j] for j in i])
        if result < temp:
            result = temp
    return result

TRY 1과 비슷하게 조합을 이용해서 풀었다. 가능한 인덱스 조합을 대입한 수들을 구해서 리스트에 모두 저장하는 방식이 아닌 result라는 변수를 할당해 이전보다 현재의 수가 더 큰 경우에 갱신하는 구조로 짜보았다. 그래도.. 결과는 역시나 시원하게 시간 초과가 나와버렸다. (미래에 컴퓨터의 성능이 초고도화+상용화가 된다면 이런 시간 초과의 늪에서 자유로울 수 있는 날도 올까?😂)

TRY 3

# TRY 3)

def solution(num, k):
    len_result = len(num)-k
    num = list(num)
    mx_idx = num.index(max(num))
    result = ''
    while len(result) != len_result:
        
        # max(num)을 선택하면 이후에 수를 다 뽑지 못하는 경우 
        if len(num[mx_idx:]) < (len_result - len(result)): 
            mx_idx = num.index(max(num[:mx_idx]))
        
        # max(num)을 선택해도 수를 뽑는 진행이 가능한 경우
        elif len(num[mx_idx:]) > (len_result - len(result)):
            result += num.pop(mx_idx)
            mx_idx = num.index(max(num[mx_idx:])) 
            
        # max(num)의 뒤에 나오는 수를 모두 뽑아야 하는 경우
        if len(num[mx_idx:]) == (len_result - len(result)):
            result += ''.join(num[mx_idx:])
            num = num[mx_idx:]
            
    return result

후.. 다시 차근차근 생각해보자..🍃는 마음으로 굿노트에 슥슥 상황을 생각해보면서 약간은 재귀적으로 풀어내고자 했다. k개의 숫자를 제거했을 때 가장 큰 수를 골라야 하므로 첫째 자리수에 최대한 큰 수를 뽑는 것이 좋겠다고 생각했다. 그런데 이 max(num)을 실컷 골랐는데 뒤에서 더이상 뽑아낼 숫자가 없거나 적은 상황이 있을 수 있으니 이를 고려하기 위해 수를 뽑아내는 진행을 방해하지 않는 선에서 최대의 수를 뽑아 나가보자는 생각으로 코드를 짜다보니

1) max(num)을 선택하면 이후에 수를 다 뽑지 못하는 경우
2) max(num)을 선택해도 수를 뽑는 진행이 가능한 경우
3) max(num)의 뒤에 나오는 수를 모두 뽑아야 하는 경우

위와 같은 진행의 단계를 고려하게 되었다. 하지만 결과적으로 테스트 케이스를 모두 통과하지 못했다. (아래 코드에 대한 반례 테스트 케이스 대환영 👼🏻)

SOL 1

현재 내 머리로 더 고민하는 건 의미가 없고 새로운 풀이와 발상에 대한 학습이 선행되어야 한다고 판단해서 구글링을 통해 다른 분들이 작성하신 코드를 어떻게든 안 체하게 꼭꼭 씹어보려고 노력했다.🤢 num, k에 따라 출력이 어디에서 어떻게 나오는지 구조적으로 파악하려고 했다. 우선 코드는 아래와 같다.

# SOL 1)

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

내부의 작동을 살펴보기 위해 아래 코드로 좀더 세밀하게 출력해보면..

# Debugging

def solution(number, k):
    answer = []
    
    for num in number: # "4177252841"
        print(f'num = {num}')
        while k > 0 and answer and answer[-1] < num:
            
            # 1
            answer.pop()
            k -= 1
            print(f'1) k={k}, answer={answer}')

        # 2
        answer.append(num)
        print(f'2) k={k}, answer={answer} \n')
        
    return ''.join(answer[:len(answer) - k])
    
print(solution("4177252841", 4) 

number에서 for문을 통해 수(num)를 하나씩 꺼내면서 answer라는 stack(stack은 리스트로 구현)에 추가해준다.

추가할 때의 조건이 이 알고리즘의 묘미인데, 기존에 있던 수(answer[-1])보다 새로 들어올 수(num)가 더 작으면 그대로 answer에 추가해주고 같거나 큰 수가 오면 해당 수보다 더 작은 수가 없을 때까지 기존의 answer를 pop() 해준다. 이렇게 하는 과정 때문에 탐욕법 이라는 방법으로 불려지게 되지 않았나 싶다. 결과적으로 answer에는 num이상의 수들만 남게 된다.

그리고 pop()을 1번 할 때마다 k의 값도 1씩 감소시켜준다. 이렇게 감소시켜주는 이유는 'k = 제거할 개수'인데 answer에 있었던 수들에서 경쟁에서 밀린(앞쪽에 내세울 값의 후보 중에서 가장 크지 않아서)수를 pop()을 통해 제거시켜줌으로써 총 제거할 개수 k 역시 감소하기 때문이다.

return에서 1️⃣을 살펴보면
'999999', k=3과 같은 입력이 주어졌을 때 answer에서 pop()되는 요소가 생기지 않아 ['9','9','9','9','9','9']를 최종 stack 값으로 가지기 때문에 len(number)-k개 만큼 앞에서부터 잘라주어야 한다.

🌵 정리

깃헙에서 전체 코드 확인하기

1. 탐욕 알고리즘(Greedy Algorithm)의 개념

탐욕 알고리즘은 현재 상황에서 가장 좋아보이는 것을 선택하는 알고리즘이다. 단순하면서 무식하게 판단하기 때문에 현재의 선택이 나중에도 최선이라는 보장이 없다. 탐욕 알고리즘은 모든 문제에 적용할 수 없고 특수한 상황에서 이용할 수 있는 알고리즘이다. 대부분의 문제는 탐욕 알고리즘을 적용했을 때 '최적의 해'를 찾을 수 없을 가능성이 높다.

• 탐욕법을 단순히 언어적으로 개념을 이해하는 것과 실제 문제를 해결하는 것 사이에는 아직 상당한 간극이 존재하는 것 같다. 이 간극을 메꾸기 위해 더 배우고 익혀야겠다.

2. stack의 활용

• stack에 최적의 값만을 남겨두고 pop()하면서 k를 줄여나가는데.. 뭔가 처음에 딱 접했을 땐 '최적의 값만이 남는다는 보장을 어떻게 하지?'라는 생각이 들었는데 stack을 통해 이전의 값에 대한 기록을 계속 누적하다가 삭제할 땐 k도 같이 줄여나가는 방식이니까 결과적으로 answer의 길이가 len(number)-k보다 크면 크지 오히려 작아지지는 않는 것 같다.