프로그래머스 - 큰 수 만들기 [파이썬]

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

프로그래머스

---

풀이 과정

어떤 숫자에서 k개의 수를 제거해서 만들 수 있는 가장 큰 수를 반환하는 문제이다.

 

 

위의 예시를 보며 잠시 생각하면 문자열의 앞에서 부터 읽어나가면서 뒤의 문자보다 작을 시, 해당 문자를 제거해주면 문제를 해결할 수 있겠다는 생각이 든다.

 

1924는 1 < 9 이므로 1 제거, 2 < 4이므로 2 제거, 이런식으로 해결하면 94가 나오고... 1231234는 같은 방식으로 3234, 4177252841은 같은 방식으로 775841이 나온다.

 

하지만 number="4321", k = 2라면 어떨까? 위의 방법을 아무리 수행해도 어떤 문자도 지워지지 않는다. 실제 답은 "43"이지만 오답 "4321"이 나올 것이다. 따라서 지운 횟수가 k보다 적다면 뒤에서 k - 지운횟수 만큼 문자를 제거해주어야 한다. (문자가 내림차순으로 정렬되어 있을 것이므로 뒤에서 지우는게 무조건 남은 숫자가 큼이 보장된다.)

 

if string[index] != '9' and int(string[index]) < int(string[index+1]):
    string = string[:index] + string[index+1:]

 

그런데 위 방법과 같이 실제 문자열 계산을 하며 문자를 제거하면 비효율적 코드로 TLE가 발생해 문제를 해결할 수도 없다. 문자열의 각 문자를 스택에 담으면서 stack top과 새로 들어올 문자를 비교하고 더 큰게 들어오면 pop() 이후 append() 연산을 하는식으로 문자 제거를 처리해주어야 효율적으로 문제를 해결할 수 있다.

---

소스 코드

def solution(number, k):
    stack = []
    for num in number:
        while stack and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        stack.append(num)
    if k > 0:
        stack = stack[:-k]
    return ''.join(stack)