[python] '큰 수 만들기' - 프로그래머스 커뮤러닝 week1

문제

1. 해결방법

원칙

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

방법

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

= * 큰 수가 앞 자리에, 작은 수가 뒷 자리에 놓이도록.
(제약조건: 뺄 수 있는 수가 k개로 제한되어 있음)

알고리즘 설계 및 구현

• 주어진 숫자 (numbers)로부터 하나씩 꺼내어 모으되
  (이 때, 이미 모아둔 것 중 지금 등장한 것보다 작은 것들은 빼낸다. 맨 오른 쪽에 있는 것들부터 왼쪽으로 살펴보면서 K개 만큼 빼낸다)
• 이렇게 모은 숫자들의 자릿수를 맞추어 반환한다.
  (아직 뺄 갯수 K를 채우지 못한 경우, 몇 개를 반환해야 한다. 자릿수를 어떻게 계산하는지 고민해야 함)

알고리즘의 복잡도

• 가장 단순무식한 방법은 어떤 것일까?
  • 가능한 모든 조합을 나열하고, 가장 큰 것을 반환한다.
  • 숫자가 커질 수록 너무 비용이 많이 들게 된다.
• 길이에 비례하는 linear type이다. =O(n) != O(n2)
• 한 번 들어갔다가, 한 번 나오는 식이므로, 길이의 제곱보다는 두 배에 가깝다.

Greedy Approach (탐욕법)

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

2. 풀이

def solution(number, k):
	collected = []
    for i, num in enumerate(number):
    # 쌓아둔 숫자들의 갯수가 1개 이상이고, 마지막 원소가 num(현재 꺼낸 요소)보다 작으며, K가 0보다 큰 경우.
    # 다음의 3개의 조건은 탐욕법에 기반하여 두 수를 비교하기 위한 전제조건임.
    	while len(collected) > 0 and collected[-1] < num and k> 0:
        	# 조건을 부합하지 않은 숫자들을 제거한다.
			collected.pop()
            # 숫자를 제거하였으므로, k의 횟수를 차감한다.
            k -= 1
       # k가 모두 제거되었을 경우, collected 변수에 남은 수를 인자삼아 리스트화 한다.
       if k == 0:
       		collected += list(number[i:])
        	break
       # 조건 만족 후, 리스트의 인자들을 이어붙인다.
        collected.append(num)
# k가 아직 0 이상의 수인 경우, 뒤에서 k개의 수 만큼의 인덱스 기준으로 끊어서 버린다.
collected = collected[:-k] if k > 0 else collected
answer = ''.join(collected)
    return answer