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

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

코딩테스트 연습 - 큰 수 만들기

 

def solution(number, k):
    # 스택을 활용한다
    stk = []
    
    # number 리스트를 순회함
    for num in number: 
        # 제거해야할 값(k)가 남아있고, stk에 값이 있고, stk의 마지막의 값보다 현재 나온수가 더 크다면 
        # (큰 숫자가 큰 자릿수를 가지게 하기 위해)
        # 스택의 마지막 숫자를 없애버리고, 제거해야할 값을 하나 줄임
        while k > 0 and stk and stk[-1] < num:
            stk.pop()
            k -= 1
        # 기본적으로 값을 한개씩 넣어줌, (위의 조건에 부합할 경우에만 스택에서 값 제거하면 큰 수만 남게됨)
        stk.append(num)
    
    # 순회를 마쳤는데도 제거할 수가 남아있다면 (ex: 999, k=2 인 경우)
    # 뒤에서 k개의 숫자는 다 제거해버림 (작은 자릿수라서 상관 없음)
    if k > 0:
        stk = stk[:len(stk) - k]
        
    answer = ''.join(stk)

    return answer

 

문제 해결 Point

스택을 활용해 숫자를 순차적으로 넣는 것이 기본 과정이다. 여기에 더해 다음에 나올 숫자가 스택의 마지막 숫자보다 크다면 스택에 있는 작은 수들은 모두 제거하는 것이 포인트이다.

 

그럼 위의 코드를 순서대로 풀어 설명해보겠다.

1. 숫자 배열을 순회한다.
2. 기본적으로 스택에 값을 하나씩 넣는다. 하지만 이 때, 앞에 조건이 붙는다.
   1. k (제거할 숫자 갯수)가 남아있고, 스택에 값이 존재하고, 스택의 마지막에 들어있는 값보다 현재 나온 num이 더 큰 경우
   2. 스택에 넣은 값을 제거하고, k도 -1 한다
3. 이렇게 순회를 마치고도 k가 0보다 크다면, (999, k=2) 와 같은 경우이다.
   이러한 경우에는 남은 k 만큼 뒷자리를 제거해버리면 된다.

스택을 문제에 적용한다는 포인트를 생각해내기가 굉장히 어려웠던 문제이다. 스택, 큐 등을 사용해 푸는 여러 유형들을 접해보는 것이 좋을 것 같다.