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

프로그래머스 레벨 2

문제 설명

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

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

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

제한 조건

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

 

---

시도 1

조합 활용해서 그냥 전부 만들기

당연히 .. 시간 초과남 ..알고 있었지만 그냥 해봤다

from itertools import combinations

def solution(number, k):
    answer = ''
    answer = max(combinations(list(number), len(number) - k))
    return ''.join(answer)

시도 2

스택을 사용하기!라는 힌트를 구글링으로..

LIFO 방식

앞자리에 큰 숫자가 오는게 무조건 큰 숫자가 되는 조건이니까 그냥 앞부터 검사하면서 제거해도 맞는 결과 나

어떻게 활용할까

가장 큰 숫자를 만들어야해

숫자를 하나하나 검사하면서 일단 저장해 그리고 다음 숫자가 더 크면 없애?

 

def solution(number, k):
    answer = []
    for n in number:
        if not answer: # 비어있는 경우 스택에 추가
            answer.append(n)
            continue
        # k가 1이상일때
        while answer[-1] < n and k > 0: # 추가하려는 값이 스택의 마지막 값보다 클때 -> 그러면 제거
            answer.pop() # 스택의 마지막 원소 제거하기
            k -= 1 # k 1 감소
            if not answer or k <= 0: # 만약 스택이 비거나 k가 0이하가 되면 break
                break
        answer.append(n) # 스택에 원소 추가
    # 987654321 반례
    # 즉 반복문을 돈 이후에 k가 0이 아니면 스택에서 원소 제거가 필요
    # k가 0보다 큰 경우 answer[:-k]까지의 범위만 리턴
    return ''.join(answer[:-k]) if k > 0 else ''.join(answer)

시도3

Code cleaning

마지막 리턴 조건 주의..answer의 길이에서 계산해야 함

while 문 조건에 있으니까 한번 더 검사할 필요 없음

def solution(number, k):
    answer = []
    for n in number:
        while answer and answer[-1] < n and k > 0:
            answer.pop()
            k -= 1
        answer.append(n)
    return ''.join(answer[:len(answer) - k])

---

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

프로그래머스