[프로그래머스] 큰 수 만들기

내 코드

def solution(number, k):
    cur=0
    delete=0
    
    while True:
        if delete == k: break  
        if number[cur] < number[cur+1]:
            if cur!=0:
                number = number[:cur] + number[cur+1:]
                cur-=1
            else:
                number = number[cur+1:]
            delete+=1
        else:
            cur+=1
        if cur == len(number)-1: break
    if k!=delete: number = number[:delete-k]
        
    return number

k개의 수를 제거하여 가장 큰 수를 구하는 문제이다.

처음에 문자열을 list로 변환해서 풀었는데 시간초과가 나왔다ㅠㅠ list를 사용할때는 list로 변환하고 pop을 해야하기 때문에 시간이 오래걸려서 그런것같다!

 

테스트케이스에 있는 number = 4177252841, k=4 를 예로 들면서 코드를 설명하겠다. 

가장 큰 수를 구해야하므로 앞의 숫자가 뒤의 숫자보다 작으면 앞의 숫자를 삭제하는 식으로 문제를 풀었다. 수가 4177252841일때 1개를 삭제해야한다면 두번째 숫자 1을 제거한, 477252841 일때가 가장 큰 수이다. 이 경우는 4,1을 비교할 때는 else문으로 넘어가고 1,7을 비교할 때 if문으로 들어가서 number[cur]을 제거한다.

이렇게 delete가 k와 같아지거나 number의 끝까지 반복했을때 while문이 멈춘다.

delete가 k일때는 답이 나오지만 number의 끝까지 반복했을때 반복문이 멈춘 경우에는 답이 나오지 않는다.

예를들어 이런 경우이다. number = 98765431, k=3 이렇게 역순으로 정렬된 경우이다. 이때는 앞의 숫자가 뒤의 숫자보다 작은 경우가 없기 때문에 k만큼 잘라주면 답이나온다.

 

다른사람 코드

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        while len(stack) > 0 and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        stack.append(num)
    if k != 0:
        stack = stack[:-k]
    return ''.join(stack)

나는 원래 number에서 삭제하는 방식으로 풀었는데 이 풀이는 stack에 숫자를 추가하는 방식으로 풀었다.

스택에 숫자하나를 넣고 다음 숫자가 앞의 숫자보다 크면 앞의 숫자를 pop하고 다음숫자를 append하는 방식이다. 만약 앞의 숫자가 더 크면 pop하지 않고 바로 append를 한다.