프로그래머스 Lv.2 | Python | 큰 수 만들기

1. 문제 정보

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

프로그래머스

• 난이도: Lv.2

---

2. 문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

제한 조건

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

---

3. 접근 기준

• k개의 숫자를 제거해 가장 큰 수를 만들기 위해서는 단순히 큰 자리 수를 제거하는 것이 아니다. 즉, 현재 숫자보다 앞에 있는 값이 작다면 제거하여 전체 자릿수의 크기를 최대화하는 방향으로 구성해야 한다.

“앞자리에서 작은 수를 제거해 큰 수가 앞으로 오도록 만들어야 한다"

---

4. 사용한 패턴 / 알고리즘

스택 + 그리디(Greedy)

• 숫자를 왼쪽부터 순회하면서 스택에 저장
• 현재 값이 스택의 top보다 크면,
  → 더 큰 수를 앞에 두기 위해 pop 수행
• 이 과정을 k번까지 반복

“앞자리에서 작은 값을 제거하는 선택을 반복하면 전체 수가 최대가 된다”

---

5. 핵심 아이디어

• 큰 수를 만들기 위해서는 앞자리에 가능한 큰 숫자를 배치해야 한다.
• 따라서 현재 숫자를 기준으로, 앞에 있는 값이 더 작다면 제거하여 더 큰 숫자가 앞으로 오도록 만든다.
• 이를 위해 스택을 사용하고,
  → 현재 값이 스택의 top보다 크면 k가 허용하는 범위 내에서 pop 수행
• 모든 순회를 마쳤는데도 k를 다 사용하지 못했다면
  → 뒤에서부터 남은 개수만큼 제거하여 자릿수를 맞춘다

---

6. 풀이 코드

def solution(number, k):
    stack = []
    
    for num in number:
        while stack and k > 0 and stack[-1] < num:
            stack.pop()
            k -= 1
        stack.append(num)
    
    # 아직 k 남아있으면 뒤에서 제거
    if k > 0:
        stack = stack[:-k]
    
    return ''.join(stack)

---

7. 핵심 로직 요약 

1. 숫자를 왼쪽부터 순회하며 스택에 저장
2. 현재 값이 스택 top보다 크면 k가 허용하는 만큼 pop하여 앞자리 값을 교체
3. 순회 후 k가 남아있으면 뒤에서부터 제거하여 최종 결과 생성

---

8. 어려웠던 점

• 초기에 스택을 활용한 방식이 아니라, 2중 for문으로 모든 경우를 비교하려다 보니 불필요한 비교가 늘어나면서 로직이 복잡해졌다.

특히 “앞자리의 작은 값을 제거해야 한다”는 기준을 명확히 잡지 못해 구현 방향을 잡는 데 시간이 걸렸다.

---