[Programmers] 탐욕법(Greedy) - 큰 수 만들기

해당 문제는 프로그래머스의 탐욕법 관련 문제를 풀고 작성한 글입니다.
프로그래머스 - 큰 수 만들기: 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의 자릿수 미만인 자연수입니다.

 

성공 코드

프로그래머스 - 큰 수 만들기: https://vg-rlo.tistory.com/251

실패 코드들

Big O of min and max: https://stackoverflow.com/questions/35386546/big-o-of-min-and-max-in-python

처음에는 탐욕법(Greedy)에 대한 이해가 부족해서 완전탐색법에 해당하는 내장함수 min을 사용하거나, max를 사용하는 풀이를 생각했습니다. 그래서 O(n)이기 때문에 number가 1,000,000(천만)으로도 주어졌을때 천만번의 loop를 돌게되는 것입니다. => 탐욕법을 써먹지 못한 잘못된 코드를 짠 것이었습니다. ㅠ 

import heapq
    
def solution(number, k):
    answer = ''
    
    # 숫자로 바꿔준다.
    num2int = [int(ch) for ch in number]
    print(num2int)

    # heap으로 min을 pop시킨다.
    for i in range(k):
        num2int.pop(num2int.index(min(num2int)))
    print(num2int)

    # 큰 숫자로 정렬을 먼저한다. 
    int2num = [str(i) for i in num2int]
    # print(int2num)

    answer = "".join(int2num)
    # print(answer)

    return answer

if __name__ == '__main__':
    nums = ['1924', '1231234', '4177252841']
    k = [2, 3, 4]

    for num, k_i in zip(nums, k):
        print(solution(num, k_i)) # 94, 3234, 775841

import heapq
    
def solution(number, k):
    answer = ''
    
    # k까지 슬라이싱 후, 그 중 가장 큰 수의 Index 추출
    num2int = [int(num) for num in number]
    max_idx = num2int.index(max(num2int[:k]))
    num2int = num2int[max_idx:]
    remain_k = k - max_idx    
    # print(num2int)
    # print(f"남은 제거 가능 개수: {remain_k}개")

    i = 0
    while(1):
        # 제거 가능 개수가 0개이면 break
        if remain_k == 0 or i == len(num2int)-1:
            break
        
        if num2int[i] < num2int[i+1]:
            num2int.pop(i)
            remain_k -= 1
        else:
            i += 1
    # print(num2int)

    answer = "".join(map(str, num2int))
    return answer

if __name__ == '__main__':
    nums = ['1924', '1231234', '4177252841', '7921']
    k = [2, 3, 4, 2]

    for num, k_i in zip(nums, k):
        print(solution(num, k_i)) # 94, 3234, 775841, 92

아래 코드는 접근법은 맞았으나, 슬라이싱이 시간이 오래걸리기 때문에 대체할 수 있는 pop이나 다른 방법을 사용해봐야할거 같습니다. 아래 코드에서 개선해야하는 부분은 max를 사용한 파트와 반복된 slicing을 하는 부분입니다. 해당 부분을 해당 블로그 코드를 참고하여 stack 개념을 활용해서 개선해야합니다.

def solution(number, k):
    # k개의 앞자리 수만 확인
    del_cnt = 0
    isstartnum = False
    start_num = max(number[:k+1]) 
    # print(start_num)

    for num in number:
        # print(f"num: {num}")
        # 제거할 수의 개수를 만족시켰을 때 break
        if del_cnt == k:
            break

        if (int(num) != int(start_num)) and not isstartnum:
            # print(int(start_num))
            number = number[1:]
            del_cnt += 1
        # 맨 앞의 큰 수가 될 숫자를 찾았을 때
        else:
            isstartnum = True
            number = number[1:]
            break

    biggest_num = str(start_num)
    for num in number:
        if del_cnt == k:
            break
        if int(num) < int(number[1]):
            number = number[1:]
            del_cnt += 1
        else:
            number = number[1:]
            biggest_num += num
    biggest_num = biggest_num + number
    return biggest_num