저번주 복습에서는 더 효율적인 코드와 새로운 풀이 방법을 고민하는 데 중점을 두었다면, 이번 주 복습에서는 이전에 학습했던 개념을 다시 익히고 정리하는 데 오롯이 집중했다.

---

문제

링크

숫자 문자열에서 정확히 k개의 숫자를 제거하여 만들 수 있는 가장 큰 수를 구하는 문제이다.

---

풀이

숫자를 순회하며 스택에 숫자를 추가하고, 현재 숫자보다 작은 이전 숫자는 제거하면서 가장 큰 수를 만들어 나가자.

가장 큰 수를 만들기 위해서는 앞자리의 값이 최대가 되어야 하므로, 현재 자리에서 더 큰 숫자가 등장했을 때 이전의 작은 숫자를 제거하는 그리디 알고리즘을 사용하자.

---

코드

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

    # 1. 숫자 문자열을 왼쪽부터 한 글자씩 순회
    for num in number:

        # 2. 현재 숫자가 제거할 수 있는 횟수(k)보다 크고, 스택이 비어있지 않고, 스택 맨 위 숫자보다 크면
        while k > 0 and stack and stack[-1] < num:
            stack.pop() # 스택 맨 위의 작은 숫자를 제거 (더 큰 숫자를 앞자리에 두어야 큰 수가 됨)
            k -= 1       # 제거 횟수 차감

        # 3. 현재 숫자를 스택에 추가
        stack.append(num)

    # 4. 순회가 끝난 후에도 제거 횟수가 남아있다면
    #    스택 뒤에서부터 남은 횟수 k만큼 제거
    #    ex) k=2, stack=[4321] → [43] (맨 뒤의 2개 제거)
    if k > 0:
        stack = stack[:-k]

    # 5. 스택의 숫자들을 이어 붙여 문자열로 반환
    return ''.join(stack)

---

생각해본것

전체 숫자에서 K개가 제거되었을때 모든경우의 조합을 구하고 최댓값을 찾으면?

from itertools import combinations

def solution(number, k):
    n = len(number)
    answer = ""

    # 1. k개의 숫자를 제거하는 모든 경우의 수를 생성한다.
    for removed in combinations(range(n), k):
        removed = set(removed)

        candidate = ""

        # 2. 제거되지 않은 숫자들로 새로운 숫자를 만든다.
        for i in range(n):
            if i not in removed:
                candidate += number[i]

        # 3. 생성된 숫자 중 가장 큰 값을 정답으로 갱신한다.
        answer = max(answer, candidate)

    return answer

생성해야할 조합이 많으면 시간이 비효율적으로 늘어나 테스트케이스를 통과하지 못했다.

---

느낀점

최상단에 위치한 코드로는 새로운 테스트 케이스를 통과했다.
같은 동작을 수행하더라도, 비효율적인 방식은 테스트케이스를 통과할 수 없던 것이다.

개인적으로 그리디 알고리즘과 최적해라고 하면 정답에 도달하는 규칙이나 공식을 먼저 떠올리는 경향이 있었다만,
이번 문제를 다시 살펴보며 단순히 정답을 맞히는 것보다 어떻게 하면 불필요한 탐색을 줄이고 더 효율적으로 답에 도달할 수 있는지를 고민하는 과정 역시 최적해를 구하는 중요한 방법이라는 점을 다시금 떠올릴 수 있었다.