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

문제 링크

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

생각의 흐름

1. 문제 파악
2. 시간 복잡도 파악
3. 스택 활용 파악
4. 코드로 구현

<문제 파악>

문제를 이해하는 것은 어렵지 않았다. k개의 자리의 수를 제거하여 결과적으로 가장 큰 수를 만드는 것. 문제를 파악하는 것은 이 문제의 핵심이 아니다.

<시간 복잡도 파악>

냅다 뛰어들어 코드를 짜면 O(N^2)으로 풀 수 있다. 처음에 그렇게 풀었다가 테스트케이스에서 시간 초과를 2~3개 맞이했다. 문제에서의 제한조건을 자세히 보자.

• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

number와 k 모두 1,000,000 까지도 갈 수 있기 때문에 O(N^2)은 절대 안 된다. 그렇다면 이 문제에서 시간복잡도를 줄일 수 있는 방법을 생각해야 했고, 그 답은 스택에 있었다.

<스택 활용 파악>

맨 처음 생각한 풀이는 숫자를 하나씩 넣으면서 그 숫자를 넣을지 안 넣을지 파악하기로 했다. 그 기준은 내 앞에 k개의 수를 파악하여 나보다 큰 것이 있으면 넣지 않고, 내가 가장 큰 것이면 넣는 것이다.
하지만 여기서 반대로 생각해보자. 내 뒤 k개를 보는 것이 아니라, 내 전에 나보다 작은 수가 있으면 삭제하고 그걸 k개 삭제될 때까지 반복하면 된다.
그럼 여기서 내 앞의 수를 나보다 큰지 확인하면서 확인 된 수는 넣어두고 계속 진행하는 자료구조, 스택이다.

<코드로 구현하기>

포인트

1. 스택 사용
2. k가 모두 소모되지 않았을 경우 파악

def solution(number, k):
    number = list(number)
    stack = []
    for i in number:
        while len(stack)>0 and stack[-1]<i and k>0:
            stack.pop()
            k-=1    
        stack.append(i)
    for _ in range(k):
        stack.pop()
    return "".join(stack)

후기

부족한 점을 찾아서 내 것으로 만들어야 한다. 하나의 방법의 풀이로 계속 붙잡고 있으면 안된다. 안 되는 방법을 다른 시각으로 보는 힘도 길러야 한다. 이 문제에서는 뒤의 k개를 봐서 안 됐으면 앞을 볼 줄도 알아야 한다. 이 생각 하나만 떠올랐으면 바로 스택이 떠올랐을 것이다.