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

 

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

분류: 탐욕법(Greedy), Lv2

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

프로그래머스

---

풀이 과정

파이썬으로 진행하였습니다.

1) 브루트 포스(Brute Force)

 

우선 가장 간단한 건, 모든 가능한 조합을 다 만들어보고 그중 가장 큰 수를 찾는 방식인 브루트 포스(Brute Force)로 만들 수도 있겠네요.

 

파이썬 라이브러리 중 itertools을 사용하면 순열(permutations) 이나 조합(combinations)를 쉽게 처리할 수 있습니다.

n-k개를 뽑는 조합을 모두 만들어봅니다.

from itertools import combinations

def solution(number, k):
    # n-k개를 뽑는 모든 조합 구하기
    n = len(number)
    comb = list(combinations(list(number), n - k))
    
    # 조합들을 문자열로 합쳐서 숫자로 변환 후 그 중에서 최댓값이 정답
    answer = max(["".join(c) for c in comb])
    return answer

 

위의 코드를 넣고 프로그래머스 테스트케이스에서 돌려보면 잘 동작하는 군요!

하지만 올바른 접근은 아닙니다. (일단 통과는 되었지만 ㅎㅎ)

조합의 경우, N이 클 때는 매우 비효율적입니다. 

 

그렇다면 그리디(탐욕법) 하게 접근해봅시다!

 

2) 그리디

탐욕적으로 접근하는 방법입니다. 즉, 매 순간 최선의 선택을 해보는 것입니다. 

가장 큰 수를 만들어야 하니 접근은 이렇습니다. 

앞자리에 큰 숫자가 올수록 전체 수가 커진다라는 걸 이용해보는 것이죠(그리디 접근에서는 이러한 방식을 떠올리는 게 중요합니다.)

 

구현코드

 

1) Stack을 활용합니다.

2) 숫자(num)를 하나씩 확인하며, 스택의 마지막 숫자보다 지금 넣으려는 숫자가 더 크면 스택의 숫자를 제거(k가 남아있을 때까지)

3) 숫자(num)를 넣습니다.

 

파이썬에서는 별도로 Stack 자료형을 지정할 필요가 없이 리스트 자료형으로 Stack처럼 활용이 가능합니다.

stack[-1]로 리스트의 가장 마지막 값을 표현합니다.

append() 를 통해 리스트의 맨 뒤에 값을 넣고, pop()을 통해 리스트의 맨 뒤 값을 빼줍니다.

만약 k가 남아있는 경우, 아직 더 제거를 해야 하므로 리스트 슬라이싱을 해줍시다!

def solution(number, k):
    
    stack = []
    
    for num in number:
        
        while k>0 and stack and stack[-1] < num :
            # print("stack에서 빠지는 값", stack.pop())    
            k -= 1
            stack.pop()

        stack.append(num)    
        # print("stack 에 넣는 값", num)    

    if k > 0:
        stack = stack[:-k]
    
    return ''.join(stack)

 

앞서 조합을 생성하는 것 대비 훨씬 효율적으로 탐색하게 됩니다.

별개로 deque(데크, Double-Ended Queue)로도 stack을 표현할 수도 있겠네요.

---

[참고] Python itertools 라이브러리 공식문서

itertools — Functions creating iterators for efficient looping