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

프로그래머스(Programmers) 큰 수 만들기 문제

난이도 : Level 2

<문제 링크>

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

프로그래머스

 

2가지 접근방식이 있다 

1. 가능한 모든 조합을 구현 후 최대값(max)을 찾기 

2. 각 숫자를 순회하면서 가장 큰수를 선택하기 -> greedy 방법 

 

 

 

1. 가능한 모든 조합을 구현 후 최대값(max)을 찾기 

-> 제한조건에 number가 1,000,000자리 까지 수가 올 수 있으므로 조합을 다 찾는 것은 매우 비효율적

from itertools import combinations

def solution(number, k):

    # 모든 가능한 조합 생성

    comb = list(combinations(number, len(number) - k))

   

    dap = []

    for i in comb:

        dap.append(int(''.join(list(i))))

    # max최대값 찾아주기              

    answer = str(max(dap))

    return answer

-> 역시 시간초과 발생 

 

 

2. 각 숫자를 순회하면서 가장 큰수를 선택하기 -> greedy 방법 

# 제일 큰수값을 저장할 빈틀 만들어서 number 값을 하나씩 비교하면서 넣음

# 빈틀에는 비교하는 number 값보다 크거나 같은 값이 들어가도록 하기

def solution(number, k):

    # 빈 틀 만들기

    lst = []

    # enumerate 함수 이용 -> 인덱스 번호와 값 불러옴

    for i, num in enumerate(number):  

    # 빈틀에 값이 있고(없으면 마지막 값 비교못함), 빈틀 마지막 값이 number값보다 작고, 남은 제거할 횟수(k)가 존재할때 반복

        while len(lst) > 0 and lst[-1] < num and k >0:

            lst.pop()

            k -=1

    # 남은 제거할 횟수(k) 없을때 멈춤

        if k == 0:

            lst += list(number[i:])  

            break

        lst.append(num)

   # 제거할 횟수(k)가 남았지만 이미 큰수값이 다 들어가 있는 경우    

    if k > 0:

        lst = lst[:-k]

    answer = ''.join(lst)

    return answer