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

🍒문제

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

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

🍒풀이

1. 큰 수 만들 리스트 collected 선언

2. number 순회

  2-1. collected에 원소가 존재하고

  2-2. collected의 마지막 원소가 비교하는 원소보다 작고

  2-3. k가 0보다 크면

3. collected의 마지막 원소 pop

4. k = k - 1

5. k = 0 이라면 number의 남은 숫자들 collected 에  붙여 넣음 (반복문 종료)

6. 비교 숫자 num을 collected에 넣음

7. 마지막 collected의 문자열을 concat

 

 

🍒코드 - 1 (시간초과)

import itertools

def solution(number, k):
    answer = ''
    n =len(number) - k
    num  = list(map(''.join, itertools.combinations(number, n)))
    
    num.sort(reverse=True)
    
    answer = num[0]
    return answer

itertools의 combinations 라이브러리를 쓰니 시간초과가 나서 다른 방법을 찾아보았다.

 

🍒코드 - 2

def solution(number, k):
    answer = ''
    collected = []
    
    for(i, num) in enumerate(number):
        #collected에 원소 존재, 마지막숫자가 num보다 작으면 뺌, k > 0 일 경우
        while collected and collected[-1] < num and k>0:
            collected.pop()
            k -= 1
            
        #다 뺐으면 남은 리스트 collected에 넣어줌
        if k ==0 :
            collected += number[i:]
            break
        collected.append(num)
        
    # k>0이면 collected 뒤에서 k개 만큼 자른다
    if (k > 0):
        collected = collected[:-k]
    answer = "".join(collected)
    return answer