[알고리즘] 프로그래머스 - 큰 수 만들기

Evan·2025년 4월 14일

greedy

알고리즘

목록 보기

9/10

큰 수 만들기

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때,
가장 큰 수를 만들려고 합니다.

예를 들어,
숫자 "1924"에서 숫자 2개를 제거하면 만들 수 있는 조합은:
→ "19", "12", "14", "92", "94", "24"
이 중 가장 큰 수는 "94"입니다.

제한 조건

number: 2자리 이상, 1,000,000자리 이하의 숫자 (문자열 형태)
k: 제거할 수의 개수 (1 이상, number 자릿수 미만)

내가 접근한 방법

1. 숫자를 하나씩 순회하며 스택에 저장

스택은 현재까지 선택한 숫자들로 구성됩니다.

2. 더 큰 숫자를 만나면 이전 숫자 제거

스택의 마지막 숫자보다 현재 숫자가 크고,
아직 제거할 수 있다면, 스택에서 제거

3. 최종 숫자 개수는 number.count - k

모두 순회한 후에도 스택에는 남은 숫자들이 있을 수 있음
제거 횟수를 다 썼는지 확인하고, 필요한 자리 수만큼 앞에서 자름

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    var stack: [Character] = []
    var removeCount = k
    
    for num in number {
        // 스택 마지막 숫자보다 현재 숫자가 클 경우, 제거
        while let last = stack.last, removeCount > 0, last < num {
            stack.removeLast()
            removeCount -= 1
        }
        stack.append(num)
    }
    
    // 앞에서부터 (number.count - k)개만 사용
    return stack.map { String($0) }
                .prefix(number.count - k)
                .joined()
}