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

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

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

 

문제를 접하고보니 백준에서 똑같은 문제를 풀었던 기억이 났다. 그때는 고민을 하다가 힌트를 보고 풀었었는데, 지금 다시 풀려고 하니 기억이 잘 나지 않았다. 이 문제를 풀면서 복습의 중요성을 깨닫게 됐다.

 

자리 수가 최대 100만인 어떤 수가 주어지고, 그 수에서 k개 만큼의 숫자를 빼서 얻을 수 있는 가장 큰 수를 구하는 문제이다.

 

단순하게 생각했을때 주어진 수 number에서 k개 만큼 뺐을때 얻는 수의 자리 수는 len(number)-k이다. 가장 왼쪽 자리의 수(값이 큰 자리 수)부터 만든다고 가정할때 number안에 존재하는 가장 큰 숫자를 선택하는 것이 최대이다. 단, 그 숫자의 앞에 있는 모든 숫자의 개수가 k보다 같거나 작아야한다. 왜냐하면 우리가 지울 수 있는 수는 k개로 한정돼있기 때문이다.

이런 방식으로 남은 수에서 가장 큰 수를 선택하고 그 수의 앞에있는 모든 숫자를 지워나가면 답을 찾을 수 있지만, 가장 큰 수를 찾는 과정에서 시간이 오래걸리게 된다. 따라서 다른 방식으로 구현할 수 있는 방법을 찾아야했다.

 

스택 자료구조를 사용한다면 선형 시간 복잡도 O(n)으로 해결이 가능하다. number의 가장 왼쪽 숫자부터 시작해서 숫자를 스택에 넣는다. 만약 현재 숫자가 스택에 담겨있는 숫자보다 크다면 현재 숫자보다 큰 숫자가 나올때까지 스택을 pop한다. 이 과정을 통해 비교적 작은 숫자를 제거해서 가장 큰 수만 남길 수 있다. pop 횟수가 k보다 커지면 더 이상 숫자를 제거할 수 없으므로 push만 할 수 있다. 만약 pop횟수가 k를 넘지 않았다면 스택에는 큰 수만 남았다는 뜻이므로 남은 횟수만큼 number의 가장 오른쪽 숫자부터 제거해주면 된다.

 

def solution(number, k):
    stack = []

    for num in number:
        while stack and k > 0 and int(stack[-1]) < int(num):
            stack.pop()
            k -= 1
        stack.append(num)

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