큰 수 만들기
문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한 조건- number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
- k는 1 이상 number의 자릿수 미만인 자연수입니다.
number k return
| "1924" | 2 | "94" |
| "1231234" | 3 | "3234" |
| "4177252841" | 4 | "775841" |
풀이 및 소스코드
입출력 예를 보면 3234보다 4332가 더 크지 않나.. 라는 생각을 했다.
문제는 Number수에서 순서는 유지하되, k개의 숫자를 지우는 것이였다.
스택을 활용한다.
스택에서 숫자를 하나씩 고르고 만약, 고른 숫자보다 스택의 마지막이 더 작다면 스택의 마지막을 k개만큼 지워나가고 스택에 추가하는 것이다.
만약 77771111, k = 2라면, 숫자는 하나도 지워지지 않을것이고, 작은 수는 뒤에 있을 것이다. 이럴 경우에 숫자의 마지막을 k개만큼 지우면 되는데, 그냥 앞에서부터 k개를 제외한 개수만큼 출력하면 된다.
import Foundation
func solution(_ number:String, _ k:Int) -> String {
var count = k
var stack = [Character]()
for num in number{
//스택의 마지막이 더 작으면 스택의 마지막을 지워나간다
while !stack.isEmpty && stack.last! < num && count != 0{
stack.removeLast()
count -= 1
}
stack.append(num)
}
////777711111, k = 2처럼 하나도 지워지지 않았을 경우 앞에서부터 출력
return String(String(stack).prefix(stack.count - count))
}