알고리즘 코드카타 107 - 큰 수 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/42883?language=python3

프로그래머스

 

문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

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

 

 

문자열에서 k개의 문자를 지워서 만들 수있는 가장 큰 수를 찾아내는 알고리즘, 쉬워보였지만 몇가지 이유로 조금 복잡했다.

단순히 가장 큰 수를 만드는 것이 아니라 순서를 그대로 유지해야하는점, 지워야하는 문자를 명확하게 특정할 수 없는 점 등이 그랬다.

 

몇가지 시행착오를 거쳐보았다. 가장 앞 자리와 다음 숫자를 비교하는 것을 반복, k개만큼 슬라이싱해서 가장 큰 수가 아닌 숫자들을 제거, 등등... 결국 가장 작은 수를 빼야하는 것은 명확했고 그 기준을 어떻게 잡아야 할지에 대한 고민을 했다.

 

그리고 앞에서부터 'k개를 슬라이싱 한 후 가장 작은 수를개를 뺀다. 그것을 k번 반복한다.'로 기준을 잡고 코드를 구성하기로 했다.

def solution(number, k):
    number = list(number)
    number = [int(x) for x in number]
    for _ in range(k):
        front_k = number[:k]
        number = number[k:]
        front_k.remove(min(front_k))
        number = front_k + number
    answer = ''.join(map(str, number))
    return answer

실패...

 

그리고 코드를 작성해보았지만 실패한 것은 물론이고 실행 시간도 오래 걸리는 문제가 있었다. 아마도 완전히 잘못생각한것같다..

 

다시 생각해보니 위에서 생각한 방법으로는 가장 앞에 있는 숫자가 뒤에 있는 숫자보다 크더라도 뒤에서 더 작은 숫자가 연속해서 나올 경우 제거가 되지 않는다는 문제가 있었다. 문제를 해결하려면 위의 코드에 추가적인 연산을 더해줘야하겠지만 이미 실행시간이 상당히 오래걸리는터라 그럴수는 없었다. 결국 다른 알고리즘을 고민해보기로 했다.

 

반대로 생각해서 문자를 number에서 제거하는 것이 아니라 새로운 리스트에 추가하는건 어떨까? 새로운 리스트에 number의 문자를 하나씩 리스트에 추가하고 그것보다 큰 숫자가 나타날 경우 앞에 있는 숫자들을 k개만큼 제거해주고 추가하는 것이다.

 

def solution(number, k):
    stack = []
    
    for n in number:
        if stack and stack[-1] < n:
            stack.pop()
            
        stack.append(n)

    return stack

 

중간과정으로 작성한 코드, stack 리스트에 number의 문자를 하나씩 추가하면서 stack의 가장 끝에 있는 숫자가 추가할 숫자보다 작을 경우 해당 숫자를 제거하도록 했다. 문제가 있다면 숫자가 k개 이상 제거된다는 것과 가장 끝에 있는 숫자가 아닌 숫자는 제거가 되지 않는 점이었다.

 

def solution(number, k):
    stack = []
    
    for n in number:
        while stack and stack[-1] < n:
            stack.pop()
            
        stack.append(n)

    return stack

 

위에서 사용한 if문을 while문으로 수정해서 지금까지 추가된 숫자보다 큰 숫자가 추가될 경우, 앞에 있는 그보다 작은 숫자를 전부 제거하도록 수정을 했다. 이제 k개만큼만 제거할 수 있도록 조건을 추가해주면 된다.

 

def solution(number, k):
    stack = []
    
    for n in number:
        while stack and stack[-1] < n and k != 0:
            stack.pop()
            k -= 1
            
        stack.append(n)

    answer = ''.join(stack)
    return answer

 

숫자를 제거할 때, k의 숫자를 하나 감소하도록 해서 최대 k개의 숫자만 제거하도록 수정했다. 이 방법으로 모든 테스트케이스를 통과했다.

...

 

하지만 실제로 제출을 하니 마지막 케이스에서 오류가 발생했다. 다른 반례가 필요할것같다..

반례를 찾아보니 stack에 투입되는 숫자가 점점 작아질 경우, 숫자를 k번만큼 제거할 수 없는 문제가 있었다. 위의 반복문에서 k가 남았을 경우 남은 k를 모두 소진하는 구문을 추가하면 될 것같다.

 

def solution(number, k):
    stack = []
    
    for n in number:
        while stack and stack[-1] < n and k != 0:
            stack.pop()
            k -= 1
            
        stack.append(n)

    for _ in range(k):
        stack.remove(min(stack))
    
    answer = ''.join(stack)
    return answer

 

반복문을 하나 더 추가해서 남은 k만큼 실행하도록 했다. 중간에 작은 숫자가 끼어있는 경우에는 위의 반복문에서 모두 걸러낼 수 있으므로 아래의 반복문에서는 최소값을 찾아서 제거하더라도 문제가 없을 것이다.

드디어 성공!