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

 

 

문제 링크

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

프로그래머스

 

 

TIL

• 순서가 유지되어야하는 경우, 스택/큐 사용
• 어차피 큰 수를 결정하는 데 가장 앞 숫자가 제일 중요하기 때문에 앞에서부터 없애도 괜찮음
• 숫자를 이용해 큰 수 혹은 작은 수를 만드는 경우, 스택을 사용한 그리디 풀이 외우기
• 앞에서 pop한 작은 수가 뒤에서 다시 push 될 수 없음 (그럼 가장 큰 수가 될 수 없음) > Greedy

 

 

Code

def solution(number, k):
    answer = []  # 결과로 반환할 숫자들의 리스트 (스택으로 사용)
    # 순서가 유지되어야하는 경우, 스택 사용
    # 어차피 큰 수를 결정하는 데 가장 앞 숫자가 제일 중요하기 때문에
    # 앞에서부터 없애도 괜찮음
    
    for n in number:
        while answer and k>0 and answer[-1]<n:
            answer.pop()
            k -= 1
        answer.append(n)
    
    answer = answer[:-k] if k > 0 else answer
    
    return ''.join(answer)

 

 

• 주어진 숫자 number를 왼쪽에서 오른쪽으로 스캔하면서, 결과 숫자를 만들기 위해 각 자리의 숫자를 결정한다.
• 숫자를 하나씩 결과 스택에 추가할 때, 스택의 마지막 숫자보다 현재 숫자가 더 크다면, 그리고 아직 k개의 숫자를 제거하지 않았다면, 스택의 마지막 숫자를 제거한다. 이 작업을 스택의 마지막 숫자가 현재 숫자보다 작거나 같아질 때까지, 혹은 k개를 모두 제거할 때까지 반복한다.
• 모든 숫자를 처리한 후, 스택에서 남은 숫자를 결과로 반환한다.
• 만약 k개를 모두 제거하지 않고 숫자를 모두 스캔했다면, 결과 스택의 끝에서 남은 k개의 숫자를 제거한다.