티스토리 뷰

728x90

https://programmers.co.kr/learn/courses/30/lessons/42883?language=swift 

 

코딩테스트 연습 - 큰 수 만들기

 

programmers.co.kr

level 2 큰 수 만들기 (그리디)

정수로 된 문자열이 주어지고, 자연수 k가 주어지면

정수 문자열에서 k개의 문자를 제거하여 얻을 수 있는 수 중 가장 큰 수를 구하는 문제

문자열에서 문자를 제거하는 것이기 때문에 문자열의 순서는 보존되어야 한다.

 

접근방법 

큰 수를 얻는게 목적인 만큼, 앞자리 수가 커야한다.

스택 하나를 두고, k개의 카드(앞으로 문자를 제거하는 걸 카드라고 표현한다)가 남아있는 한

새로 들어갈 수가 현재 스택의 맨 위의 수보다 커야한다.는 로직이면

가장 큰 수를 얻을 수 있다.

 

오답노트

이전 코드로 테스트케이스 12번이 통과가 안돼서 반례인 9991, k=2를 넣어봤더니, 99가 결과로 나와야 하는데, 9991이 결과로 나왔다.

n-k개의 문자열을 다 채우면 stack에 푸시되면 안된다는 조건이 없어서 였다.

if문으로 append하는 조건을 추가해줬고, 통과됐다.

 

소스코드

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    var answer = ""

    var _k:Int = k
    let numbers:[Character] = Array(number)
    let n:Int = numbers.count
    var stack:[Character] = []
    
    for (i,num) in numbers.enumerated() {
        while !stack.isEmpty && _k > 0 && 
        stack.last!.wholeNumberValue! < num.wholeNumberValue! {
            stack.removeLast()
            _k -= 1
        }
        if stack.count < n-k {
            stack.append(num)
        }
    }
    return String(stack)
}
728x90
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/05   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함