Step 4: 탐욕법(Greedy) 대표 문제 풀이: 큰 수 만들기

문제 분석

큰 수 만들기 원칙

• 앞 자리에 큰 수가 오는 것이 전체를 크게 만든다
  • 따라서, 큰 것을 우선해서 골라 담고 싶다.

큰 수 만들기 - 방법

• 앞 자리에서 부터 하나씩 골라서 담되,
  지금 담으려는 것보다 작은것들은 도로 뺀다.
  단, 뺄 수 있는 수효에 도달 할 때까지만

• 큰 수가 앞자리에 작은 수가 뒷자리에 놓이도록
  (제약조건) 뺄 수 있는 수의 개수

알고리즘

탐욕법(Greedy Approach)

• 앞 단계 에서의 선택(앞 자리에 큰 수) 이 이후 단계에서의 동작에 의한 해(solution)의 최적성(optimality) 에 영향을 주지 않음

알고리즘 설계 -> 구현

• 주어진 숫자 (number) 로부터 하나씩 꺼내어 모으되
  • 이 때, 이미 모아둔 것 중 지금 등장한 것보다 작은 것들을 빼낸다.
    • 지금까지 모은 것중 오른쪽부터 살펴본다

• 이렇게 모은 숫자들을 자릿수 맞추어 반환한다.
  • 아직 뺄 개수 (k) 를 채우지 못한 경우
    • 낮은 자리수의 숫자부터 빼낸다

코드

def solution(number, k):
    collected = []
    for i, num in enumerate(number):
        while len(collected) > 0 and collected[-1] < num and k > 0:
            collected.pop()
            k -= 1
        if k == 0:
            collected += list(number[i:])
            break
        collected.append(num)
    collected = collected[:-k] if k > 0 else collected
    answer = ''.join(collected)
    return answer

알고리즘의 복잡도

• 이렇게 설계한 알고리즘의 복잡도는?
  O(N)