[Programmers] 큰 수 만들기(Python) / Greedy

programmers.co.kr/learn/courses/30/lessons/42883?language=python3

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

 

난 개인적으로 어려웠던 문제다.

Greedy 알고리즘은 뭔가.. 쉽고도 어려운 알고리즘이다.

stack 으로 구현한 Greedy한 풀이.. 어려워서 다른 사람 풀이를 참고했다.

• stack에 값이 있고, k가 남아있다면 stack의 마지막 값과 현재 value를 비교해
• value가 크다면 k를 사용하며 stack의 마지막 값을 빼준다.
  • 앞에서부터 탐색하며 비교해주기 때문에 k를 다 써버린다면 뒷 부분은 사실 그리디하게 풀 수 없기 때문에 최적해가 아닌 경우가 발생할 수 있겠다.
  • 그리디의 약점이 무조건 최적해를 보장하지는 않는다는 이유를 알 수 있다.
    

 

파이썬 코드는 다음과 같다.

---

def solution(number, k):
    stack = []
    for value in number:
        while stack and stack[-1] < value and k > 0:
            stack.pop()
            k -= 1      # 뽑아낸 갯수 -1 
        stack.append(value)
    if k > 0:       # k가 남아 있는 경우
        stack = stack[:-k]

    return ''.join(stack)

---

* 고찰 : 그리디다운 발상을 해내기 쉽지 않다 O_O.. 아무래도 연습이 많이 필요할 것 같다. 

Greedy는 순간에만 가장 큰 이득을 취하기 때문에 늘 최적해를 보장하는 것은 아니다!