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

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의 자릿수 미만인 자연수입니다.

 

입출력 예

풀이

가장 큰 수를 만들기 위해서는 제거할 수 있는 범위에서 가장 큰 수보다 순서상으로 앞에 있는 숫자들을 제거하면 된다.
예를 들어 숫자가 2314....고 k = 3보다 크다면 3개까지 제거할 수 있으니 4번째 숫자 즉 2 3 1 4 중 가장 큰 수 4를 남기고 나머지 2 3 1 을 제거하면 가장 큰 숫자가 나온다.

이렇게 숫자들을 제거 했을때 k가 0이 되면 멈추고 k가 0보다 크면 4보다 다음 숫자부터 k칸 떨어진 숫자 까지 중 가장큰 숫자보다 순서상 앞에 존재하는 숫자를 제거하는 행위를 반복하면 된다.

위의 방법으로 

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

    count = 0
    number = list(number)
    
    while k > 0 :
        temp = number[count:count+k+1].index(max(number[count:count+k+1]))
        #print(f"{number[count:count+k+1]}  {max(number[count:count+k+1])} {temp}")
        for i in range(temp):
            del number[count]
            k -= 1
        count += 1
    answer = ''.join(number)
    
    return answer

이런 식으로 코드를 구현했었다.
문자열로 받은 number을 list로 변환하여 하나씩 접근하고 수정할 수 있게 해주었고 count와 k(삭제 가능 횟수)를 이용하여 배열의 범위를 지정하여 연산하였다.
답은 구할 수 있지만 index max 함수를 이용하고 del을 이용하여 맨 앞의 항목을 지우기 때문에 시간이 너무 많이 소모된다.
(파이썬에서는 특정한 k번을 삭제하면 k+1번부터 맨 마지막 항목까지 1칸씩 당겨지기 때문에 0번을 삭제하는 경우 n번의 연산이 추가로 필요하다.)


max와 index del항목을 최적화하면 시간 내에 답을 구할 수 도 있지만 시간 초과의 경우 새로운 알고리즘을 사용하는 것이 더 정답일 것이라고 생각했다.

현재의 값을 저장한 뒤 다음에 나오는 값이 현재 값보다 크면 교체하고 작다면 이어 붙이는 방법을 이용하는데
가장 최적의 자료구조는 스택이라고 생각해서 스택을 통하여 구현하였다. 

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

    number = list(number)
    
    big_stack = [number[0]]
    
    for i in number[1:]:
        while len(big_stack) > 0 and big_stack[-1] < i and k > 0:
            big_stack.pop()
            k -= 1
        big_stack.append(i)
    
    for i in range(k):
        big_stack.pop()
    
    answer = "".join(big_stack)
    
    return answer

0번 항목을 stack에 넣은 뒤 스택 가장 위에 있는 값이 지금 들어오려는 값보다 큰지 확인하였다.
처음에는 조건을 if를 이용하여 구현하였었는데 그 경우에는 스택의 top에 있는 값만 변경되고 이 전에 들어갔던 값의 경우 변경되지 않아 while을 이용하여 삭제할 수 있는 횟수 k가 모두 소모되거나 스택이 빈 경우가 아닌 이상 끝까지 판별하게 설정하였다.

이렇게 구현하면 max나 index등을 이용할 필요가 없고 최대 number의 길이만큼만 stack에 삽입 삭제하기 때문에 짧은 시간에 답을 얻을 수 있다.