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

해결 포인트✨

 

1. 처음에 수의 앞자리와 그 뒷자리를 비교하는 걸 chance를 소진할 때까지 반복하도록 짜면 되겠다고 생각했는데, 시간복잡도가 너무 커 효율성 테스트를 통과하지 못했다.

 

2. 수 각 자리를 담은 리스트에서 인덱스를 찾아 pop 하는 걸 반복한 것이 시간복잡도를 잡아먹는 것을 발견했다.

(원래 pop은 O(1)만 걸린다고 생각했는데, 맨 끝자리를 pop하는 게 아니라, 지정해준 인덱스를 pop할 때는 리스트를 훑어야 하기 때문에 O(n)이 걸린 것이 원인이었다.)

 

3. 논리는 마찬가지로 유지하되, stack을 활용하는 것으로 코드를 수정했다. 각 자리 수의 인덱스를 따로 저장하거나 수를 삭제하는 과정에서 리스트를 추가적으로 훑을 필요가 없어져 효율성테스트를 통과했다!

 

---

코드✨

def solution(number, k):
    answer = ""
    chance = k
    stack = []
    
    for k in range(len(number)):
        while len(stack)>0 and number[k] > stack[-1] and chance>0:
            stack.pop()
            chance-=1
        stack.append(number[k])

    return ''.join(stack[:len(stack)-chance])