[PG/Python] 큰 수 만들기

📌 문제

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

코딩테스트 연습 - 큰 수 만들기

 

📌 문제 접근 방법

1. 처음엔 숫자의 길이에서 k만큼을 빼서 필요한 만큼 숫자를 뽑아내는 방식으로 코드를 짰다.
   8, 10번에서 시간초과가 나서 슬라이싱을 deque의 popleft로 바꿔봤는데도 시간초과가 났다.
2. 결국 해결하지 못하고 구글링...😅 스택을 활용한 방법으로 바꿨다!
3. 스택에 숫자를 하나씩 넣고
4. 만약 push하려는 숫자가 스택의 마지막 숫자보다 작다면 스택의 마지막 숫자가 크거나 같아질 때까지 pop을 한다.
5. 반복문이 끝나고 원하는 길이만큼 스택을 슬라이싱해서 answer에 저장한다.

 

📌 코드

from collections import deque

def find_max(number, need):
    idx = -1
    num = 0

    for i in range(len(number)-need+1):
        if int(number[i]) > num:
            idx = i
            num = int(number[i])
    
    return num, idx


def solution(number, k):
    # 필요한 자릿수 = len(number) - k
    # -> 이만큼의 숫자를 뽑는다!

    need = len(number) - k
    number = deque(number)
    answer = ''

    while number and need:
        if len(number) == need:
            while number:
                answer += str(number.popleft())
            break

        num, idx = find_max(number, need)

        answer += str(num)
        for _ in range(idx+1):
            number.popleft()
        need -= 1

    return answer

→ 시간 초과

 

def solution(number, k):
    stack = []

    for num in number:
        while k and stack and stack[-1] < num:
            stack.pop()
            k -= 1
        stack.append(num)
    
    answer = ''.join(stack[:len(number)-k])
    return answer