[프로그래머스][그리드 알고리즘] 큰 수 만들기

프로그래머스

 

1. 문제설명

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

 

2. 제안사항

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

 

3. 입출력 예

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

 

4. 풀이 과정

 

그리디 알고리즘이라 아주 단순하게 생각했다. 모든 자리를 뺀 조합을 모두 비교한 후에 가장 큰 값을 choise하는 방식으로 k만큼 반복했다.

 

단순해서 풀이도 쉽지만 당연하게도 시간초과가 나왔다.

 

그 후 한참을 고민하다가 스택 방식을 사용했다.

아주 간단한 규칙이다. 가장 큰 자리수가 최대한 큰 값을 넣는것이 가장 큰 수일 수 있다. 즉 스택의 가장 위에값을 다음에 들어갈 값과 비교해서 스택의 값이 작으면 빼버리고 같거나 크면 새로운 값을 스택에 삽입한다. 이런 방식을 이용해서 쌓여가면 자연스럽게 자릿수도 바뀌게 된다.

 

코드와 결과는

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

실패다.

 

그 후로 한참 테스트 12번에 대해 고민하다 생각이 안나 질문하기를 찾아보았는데 생각지 못한 예외 케이스를 찾았다.

한 분이 친절하게 같은 고생하지 말라고 적어주셨는데 진작에 찾아볼걸 그랬다.

 

그 case는 number = 987654321, k = 5인 경우이다.

즉 내림차순이다.

 

그래서 k값이 남는 경우가 생긴다. 이에 대한 예외를 생각하여 반복문을 하나 더 넣어주는것이다.

 

def solution(number, k):
    answer = ''
    re_numbers = []
    
    for i in number:
        while re_numbers and i > re_numbers[-1] and k > 0:
            re_numbers.pop()
            k -= 1
        re_numbers.append(i)
        
    while k > 0:
        re_numbers.remove(min(re_numbers))
        k -= 1
    return ''.join(re_numbers)