[Programmers] 큰 수 만들기

문제 설명

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

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

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

제한 조건

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

입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

문제 해설

number의 자리수가 1000000까지 되기 때문에, k개를 뺀 모든 숫자를 비교하는 완전 탐색을 하면 무조건 시간초과가 난다.

 

입력에서 숫자 하나를 하나씩만 지워가며 큰 수를 남길 때, 최종 결과값은 최적해랑 같다.

1924가 있을 때, 1924 -> 924 -> 94가 되어 최적해가 된다.

그렇다면, 1개씩 지울 때, 어떤 수를 지워야 할까?

숫자 문자열을 앞에서부터 탐색하며, 앞에서 나온 숫자가 뒤에 나온 숫자보다 작을 경우 앞에 나온 숫자를 제거하면 된다.

또한, 이러한 패턴이 여러 개 보일 경우, 가장 앞에 있는 패턴에서 숫자를 제거한다.

이를 증명하려면 귀류법을 활용하면 되고, 이 내용은 따로 적지는 않는다.

 

결과적으로는, 위의 방법을 k번 반복하면 최적해가 나오는데, 매 번 문자열을 처음부터 탐색하는 것은 비효율적이다.

stack을 이용하면 알고리즘의 최적화가 가능하다.

1. 문자열을 맨 앞에서부터 탐색한다.
2. 만약 stack이 비어있거나 stack의 마지막 값보다 작을 경우 stack에 숫자를 넣는다.
3. 만약 stack의 마지막 값보다 클 경우, stack의 마지막 값이 크거나 같아질 때까지 stack에서 pop한다.
4. 이렇게 제거된 개수가 k가 될떄까지 반복한다.
5. 만약 제거된 개수가 k보다 작을 경우(모든 숫자가 내림차순으로 정렬되어 있음) 부족한 개수만큼 뒤에서 제거한다.

 

이를 구현한 코드는 아래와 같다.

def solution(number, k):
    cnt = 0
    answer = [number[0]]

    number = number[1:]
    for n in number:
        if cnt == k:
            answer.append(n)
            continue
        while answer and int(answer[-1]) < int(n):
            answer.pop(-1)
            cnt += 1

            if cnt == k:
                break
        answer.append(n)
    if cnt!=k:
        answer = answer[:-(k-cnt)]
    return "".join(answer)