[코딩 테스트 연습(파이썬/Python)] 프로그래머스 _ 큰 수 만들기

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

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

[문제 설명]

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

[제한 조건]

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

처음에 10번만 시간초과가 떴다. 로직 자체는 문제가 없으나, 매번 number의 일부를 slicing 해야하므로, k가 크고 반복해야하는 횟수가 많은 경우 비효율적일 수 있다. 각 자리에 위치할 수 있는 k+1개의 후보 중에서 max를 탐색하기 때문에, 숫자들이 다양하게 분포되어 있으면 효율성이 높아진다.

# 10 시간초과
def solution(number, k):
    length = len(number) - k
    answer = ''
    i = 0
    while len(answer) < length:
        tmp = number[i:i+k+1] # 얘가 비효율의 원흉인듯
        num = max(tmp)
        answer += num
        j = tmp.find(num)
        k -= j
        i += j + 1
        if k ==0:
            answer += number[i:] 
            break
    return answer

애를 먹었는데, 결국 slicing을 없애는게 포인트였다. 앞에서부터 최댓값을 찾아 넣고, number를 계속 줄여나갔다.

# 통과
def solution(number, k):
    length = len(number) - k
    answer = ''
    while len(answer) < length:
        i = 0 
        num = "-1"
        for x in range(i, i+k+1):
            if num == '9':
                break
            if num < number[x]:
                num = number[x]
        answer += num
        j = number.find(num)
        k -= j
        i += j + 1
        number = number[i:]
        if k ==0:
            answer += number
            break
    return answer

사실 알고보면 stack과 유사한 방법이기 때문에, stack으로 구현하는게 가장 좋았다. 예를들어 88888을 쌓아둔 상태에서 뒤에 9가 나오고, 충분히 숫자가 남은 경우 모든 8을 빼고 9를 쌓아야 하는 것이 까다롭게 느껴졌는데, 구현해놓은 사람이 있었다...

앞에서부터 제거해나가기 때문에 사실 그렇게 복잡한게 아니었다. k를 기준삼아 생각하면 되고, k=0인 경우만 잘 신경써주면 되었다. while문 안에 stack.pop()을 위치시켜 반복해서 마지막 숫자를 빼낼 수 있게 한 것이 인상적이다.

역시 갈 길이 멀구나,,

# 스택 활용
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)