Programmers _ 큰 수 만들기 _ 파이썬

📃 문제

프로그래머스 큰 수 만들기

알고리즘 - 탐욕법 (Greedy)

매 순간 최적의 해를 선택한다.

조건

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

• 결과 값은 len(number)-k 자리의 "문자열" 형태

💡 풀이 과정

1) combination 🤯

시간초과

from itertools import combinations
def solution(number, k):
    maxnum = 9
    c = combinations(number, len(number)-k)
    for ci in c:
        num = int(''.join(ci))
        print(num)
        if num > maxnum:
            maxnum = num
    answer = ''
    return str(maxnum)

combination 함수는 O(2^N) 의 시간복잡도를 가지기 때문에 최대 길이에서 10초를 넘길 수 밖에 없습니다.

2) Brute-force 🥳

• Idea :
  시작할 수 있는 위치 중 젤 큰 수에서 시작하면 된다.
  만약 "4444777711119999"에 K=4이면 뒤의 1111보다 앞의4444가 사라져야한다.

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

🔍 정리 & 배운 것

Stack
Last In First Out : 최근에 들어온 값을 가장 먼저 삭제한다.

List 문법
list.pop() : 맨 뒤에 값 제거
list.remove(x) : list에서 첫번째로 등장하는 x값 찾아 제거

• 참고 1