[프로그래머스] Level2 큰 수 만들기(python)

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

 

1. 시간 초과가 발생한 풀이(투포인터)

-  number의 길이가 1,000,000 자리 수 까지 가능하기 때문에 시간복잡도를 꼭 고려해야하는 문제이다.

- 처음에 투 포인터를 이용해 풀었는데, 테스트 케이스 2개(8,10번)의 시간초과를 못 해결해 장렬하게 전사했다.

def solution(number, k):
    answer_len = len(number) - k
    start = 0
    end = 1
    number = list(number)
    
    while k>0 and end != len(number):
        if number[end] > number[start]:
            number.remove(number[start])
            k -= 1
            start = 0
            end = 1
        else:
            start += 1
            end += 1

    if len(number) != answer_len:
        number = number[:-k]
    
    answer = ""
    
    for i in number:
        answer += i
        
    return str(answer)

 

- 간단하게 설명하자면 start 와 end 라는 두 개의 포인터를 만들고, end가 가르키는 값이 더 크면 start가 가르키는 값을 제거한다.

- 본 과정을 통해 수의 오름차순 정렬이 완성됐다. 따라서 남아있는 len(number)가 answer_len 보다 큰 경우는

  같은 숫자의 반복 혹은 오름차순의 순서일 것이기 때문에 제일 끝에 있는 k개를 제외하고 출력한다.

 

 

2. stack을 이용한 풀이

- 통과는 했지만 테스트케이스 10번이 아슬아슬 했기 때문에 리팩토링이 필요하다.

def solution(number, k):
    stack = []
    i = 0
    
    while i != len(number): #number의 끝까지 다 확인하면 break
        
        #stack에 남아있는 개수 + 확인하지 않은 number의 개수가 k개를 제거한 길이이면 멈춘다
        #자릿수가 큰게 클 수록 이득이다. 앞에서 k개를 제거했고, 제일 큰 수를 만들었기 때문에 멈춰도 괜찮다
        if len(stack) + len(number[i:]) == len(number) - k:
            break
        
        #stack에 아무것도 들어있지 않으면 push
        if len(stack) == 0:
            stack.append(number[i])
            
        #stack에 숫자가 들어있고, top보다 number이 크면 top을 뺀다.
        #top보다 number이 클 때까지 이 과정을 반복한다.
        elif len(stack) > 0 and stack[-1] < number[i]:
            stack.pop(-1)
            continue
        
        #stack에 숫자가 들어있고, top보다 number이 작으면 push
        else:
            stack.append(number[i])
            
        i += 1
        
    answer = ""
    
    for j in stack:
        answer += j
    
    for j in number[i:]:
        answer += j
    
    #위 과정을 통해 수가 오름차순정렬 되었다.
    #len(answer)이 len(number)-k보다 큰 경우는 같은 수가 반복되어 있거나, 처음부터 오름차순이 잘 되어있던 경우라서
    #마지막 k개를 제외하고 return 하면 된다.
    if len(answer) > len(number) - k:
        return answer[:-k]
    
    return answer

 

 

3. 리팩토링

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)

위와 비슷한 풀이인데 훨씬 더 간단하게 풀 수 있다.

 

 

 

 

 

시간 차이가 어마어마 하다 😥

 

 

이 문제의 키포인트는 stack을 이용해 한 번 정리하고 나왔는데도 길이가 number-k가 아닐 때 인 것 같다.