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

 문제

 

 

 문제 상황

 

- 숫자 string과 제거할 숫자의 개수를 입력받아 숫자를 제거하여 얻을 수 있는 가장 큰 숫자를 찾는다.

 

 해결 전략

 

- number의 자리가 최대 100만 자리

 

 코드

 

def solution(number, k):
    stack = ["0"]
    # 처음 빈문자를 넣었으므로 0을 지우기 위해 k를 하나 증가시킨다.
    k += 1
    for i in range(len(number)):
        if k == 0:
            stack.append(number[i])
            continue
        while k > 0:
            # 비어있지 않으면 number[i]로 계속 비교해 나간다. stack의 마지막 값보다
            # number[i]가 더 크면 stack[-1]을 제거해 나간다.
            if number[i] > stack[-1]:
                stack.pop()
                k -= 1
            if len(stack) == 0 or number[i] <= stack[-1] or k==0 :
                stack.append(number[i])
                break
    if k != 0:
        stack = stack[:-k]
    return ''.join(stack)

 

 

 

 해설

 

- 10번 케이스의 시간 초과와 12번의 런타임이 문제의 핵심이었다.

 

- 스택을 이용해서 조건을 통해 시뮬레이션 하였다. 어떤 문자를 입력받을 때 그 문자를 순회하면서 스택에 있는 마지막 숫자와 비교하여 순회하는 숫자가 더 크면 스택의 마지막 숫자를 제거하고 k를 갱신하며 비교를 하였다.

 

- 문제는 마지막인데 같은 숫자가 연속적으로 존재할 경우 숫자가 제거되지 않는다. 그래서 k가 0이 아니면 끝에 숫자를 k만큼 제거하는 것으로 처리하였다. 

 

- 속도는 n만큼 안에서 약 k만큼 돌기 때문에 O(N*M) 일 것 같다. N이 최대 100만이고 M이 최대 k의 자릿수인 7이므로 속도는 1억을 넘지 않아 충분하다.

 

 새로 학습한 것 & 실수 

 

- list의 길이가 무수히 길어지면 숫자로 변환하여 int를 비교하여 추가, 제거하는 것보다 str으로 비교하는 것이 속도가 더 빠르다.

 

- 문제를 바로 풀기보다 고민을 하여 해법을 명확히 하고 구현을 시작해야한다.

 

- 이 문제의 경우도 반례를 생각하지 못해 코딩을 고쳐나가는 구조로 풀었다.

 

 

 

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