[탐욕법 / 프로그래머스] 42883번 : 큰 수 만들기

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42883

 

Lv2 문제고, 드디어 (3번째 풀이만에) 스스로 풂! 

 

풀이 로직

순차적으로 진행하면서 만나는 숫자 중 들어온 것보다 큰 경우가 있을 때만 answer에 넣어주면 된다 

number의 가장 왼쪽에서 오른쪽으로 진행하면서 3가지 조건을 만족할 때 숫자를 제거한다 

• 제거할 횟수가 남아있을 때 (K > 0)
• 제거할 숫자가 있을 때 (answer)
• answer 가장 끝 숫자가 새로 들어올 숫자보다 작을 때 (answer[-1] < number[i])

위 경우에 숫자들을 제거하고, 아닌 경우는 answer에 추가해준다 

number의 길이에서 k번을 제거했으니 answer에서 n - k 만큼의 길이만큼 인덱싱해서 반환해주면된다

(어차피 k번 제거해서 길이가 n - k이겠지만, 43344 k = 3인 경우에 answer = [4, 4, 4] 가 나온다. 이때 답은 44가 나와야하므로 n - k를 해준다)

 

 

 

- 정답 풀이 : 

def solution(number, k):
    answer = []
    n = len(number)
    K = k
    for i in range(len(number)):
        while K > 0 and answer and answer[-1] < number[i]:
            K -= 1
            answer.pop()
        answer.append(number[i])
        
    return ''.join(answer)[:n - k]