[프로그래머스] 큰 수 만들기 (Lv2, Python3)

문제

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

풀이

기본 아이디어

주어진 string 과 제거해야하는 자릿수 k는 이미 정해졌으므로,
answer의 자릿수도 len(string) - k 로 정해진 셈

각 자릿수에 가능하면 큰 수가 오게끔 제거해나가면 되므로.
바로 뒤에 위치한 숫자보다 작다면 제거해서 앞으로 땡기면 됨

틀린 solution.py

• 뒷자리와 비교하면서 작으면 제거하고 맨앞으로 다시 돌아가서 다시 스캔하는 식이라, 일부 케이스에서 시간이 너무 오래걸림
• data type의 문제보다 알고리즘의 문제라list 든, deque 든 마찬가지로 오래걸림

def solution(number, k):

    num_list = [int(n) for n in number]

    while k > 0:

        for i in range(0, len(num_list)-1):
            if num_list[i] < num_list[i+1]:
                num_list.pop(i)
                k -=1
                break
            else :
                i+1

    answer = ''.join(map(str, num_list))

    return answer

다시 아이디어 : stack 사용

비교하고 다시 앞으로 돌아가는게 오래걸리는거니까,
앞에 자리수 비교해서 지울때 계속 앞으로 가면서 비교하면 다시 앞에서부터 안돌아도 됨

number 앞에서부터 넣으면서

• stack[-1] 보다 작거나 같은 경우 그냥 넣고
• stack[-1] 보다 큰 경우 더 큰 수가 나올때까지 다 빼고 넣음 (이 때, k -= 1)

테스트케이스 12번 틀린 solution.py

def solution(number, k):
    answer = ''

    stack = [number[0]]

    for n in number[1:]:
        # stack이 비어있지 않고, stack 가장 끝이 n보다 작다면
        while stack and stack[-1] < n :
            # 더 뺄 수 있으면 뺀다
            if k > 0:
                stack.pop()
                k -= 1
            # 더 뺄 수 없으면 그냥 넘어감
            else :
                break
        # n을 stack에 추가
        stack.append(n)
                
    return ''.join(stack)

끝까지 다 비교했으나 k > 0 인 케이스가 있다.

예) 앞에서부터 비교하면서 순서대로 넣을때 pop이 한 번도 없는 케이스 987654321

이 경우 그냥 k만큼 pop 하면 됨

solution.py

def solution(number, k):
    answer = ''

    stack = [number[0]]

    for n in number[1:]:
        # stack이 비어있지 않고, stack 가장 끝이 n보다 작다면
        while stack and stack[-1] < n :
            # 더 뺄 수 있으면 뺀다
            if k > 0:
                stack.pop()
                k -= 1
            # 더 뺄 수 없으면 그냥 넘어감
            else :
                break
        # n을 stack에 추가
        stack.append(n)
    
    # number 끝까지 다 봤는데 k 남은 경우, stack 끝에서 그만큼 빼버리면 됨
    while k > 0:
        stack.pop()
        k -= 1
    
    return ''.join(stack)

Note

1. 아이디어는 맞아도 효율적인 자료구조를 떠올리는(...)게 관건
2. index로 접근하여 제거하는 list.pop(idx) del deque[idx] 는 list나 deque이나 시간 많이 잡아먹는다.