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

사용 언어 - Python3

문제 - 큰 수 만들기

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

프로그래머스

 

 

정답

스택

리스트의 pop, append 이용

 

1. 시간초과 오답

가능한 모든 조합을 구한후, 최대값 출력

from itertools import combinations
def solution(number, k):
    result = list(combinations(list(number),len(list(number))-k))
    lst = []
    for r in result:
        lst.append("".join(r))

    return max(lst)

 

2. 스택 사용하기

십의 자리 숫자가 클수록 큰 값이다.

만약 number에서 빼야 하는 숫자가 있고, k > 0

answer 스택에 숫자가 들어있고,

answer 스택에 마지막 숫자가 현재 n보다 작다면, answer[-1] < n

작은 숫자를 pop해주고, 현재의 n을 append해준다. 작은 값 한개를 삭제했으므로 k -= 1

예) number = 1924, k = 2

answer = []

answer = [1]

answer = [1], 1 < 9 => 1을 pop! , k=1

answer = [9]

answer = [9,2]

answer = [9,2], 2 < 4 => 2를 pop!, k=0

answer = [9,4]

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

    for n in number:
        while k > 0 and answer and answer[-1] < n:
            answer.pop()
            k -= 1
        answer.append(n)

    return ''.join(answer[:len(answer) - k])

 

 

 

레퍼런스

https://chiefcoder.tistory.com/37