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

이번에는 큰 수 만들기에 대한 문제이다.

 

큰(?) 함정도 있고, 그리디 치고는 길이 잘 보이지 않았다.

강의를 통해 배운 내용을 정리해 보았다.

 

알고리즘

알고리즘은 간단하다.

1. 맨 앞부터 한 자리씩 정답의 후보라고 생각하고 쓴다.

2. 만일 새로 쓸 수가 직전에 쓴 수보다 크다면 지워버린다. 그 앞도 비교하여 지워버린다.
   새로 쓸 수보다 직전의 수가 더 크다면 새로 쓸 수를 써버린다.

3. 단, 지울 수의 개수는 정해져 있으므로, 지울 양이 채워졌으면 지우는 것을 중단해버리고 남은 수를 모두 다 쓴다.

하지만 여기서 큰 함정이 있는데, 이대로 할 경우 987654 처럼, 숫자가 지워지는 경우가 없는 경우가 있다.

이때는, 뒤에서부터 숫자를 지워버리면 되는데, 굳이 이러한 경우를 고민할 거 없이 최종적으로 수를 쓰고

4. -k번째 자리까지 슬라이싱 해버린다. 단 k = 0일 경우 이미 다 뺐으므로 그냥 원래 쓴 숫자를 돌려준다.

 

코드

코드에서 유심히 봐야 하는 부분은 바로 enumerate. number을 한 자리씩 주면서 동시에 index i도 같이 넘겨주는 방법으로 enumerate를 사용하였다. 

# 모범답안
# 복잡도 : O(n)임에 주의한다.
def solutuon(number, k):
    collected = []
    for i, num in enumerate(number):
        # i는 index
        # num은 숫자
        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