탐욕법 - 큰 수 만들기

아래 문제는 프로그래머스에서 제공하는 코딩테스트 > 탐욕법 > 큰 수 만들기 (고득점 Kit)의 문제입니다🧑🏻‍💻

 

문제 제시

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

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

제한 조건

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

입출력 예

"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

문제 해결

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    let numberCount: Int = number.count
    let numbers = number.map{ String($0) }
    var stack = [String]()
    var count = 0
    
    for i in 0..<numberCount{
        while count < k && !stack.isEmpty && stack.last! < numbers[i] {
            stack.removeLast()
            count += 1
        }
        
        if count >= k {
            stack.append(contentsOf: numbers[i...])
            break
        } else {
            stack.append(numbers[i])
        }
    }
    return String(stack.joined().prefix(numberCount-k))
}

사용된 개념

 - map

 - 조건/반복문

 - 배열

 

문제 뒷담화

이번 문제의 핵심은 배열에 넣어주고 비교해주며 결과를 도출해내는것이였다.

먼저 numberCount는 입력된 배열의 수를 담아주었는데, 한번돌때 시간 복잡도가 O(n)임으로 2번 이상 쓰인다면 저렇게 미리 빼서 상수로 지정해주는것이 더 효율적이였다.

그 뒤, 문자열이 주어짐으로 문자로 구분지어주기 위해 노력하였는데 그럴 필요없이 문자열로 매핑시켜주면 되었다.

문자열을 문자로 변환해줄때는 아래와 같이 직접 구현해주면서 조건문을 돌아봤다.

// 1번 방법
let arr = Array(number)

// 2번 방법
var arr = [Character]()
for i in number {
    arr.append(i)
}

그러고 난 뒤 문자열 길이 만큼 조건을 돈다.

첫번째 조건은 주어진 삭제갯수만큼 카운트를 체크하여 작고 스택이 비지않았으며 스택의 마지막 요소가 비교하려는 값보다 작다면 스택의 마지막 요소를 삭제하고 삭제된 갯수 카운트를 늘려주며 while문을 돌았다.

그리고 카운트가 주어진 k보다 크거나 같으면 삭제 조건을 성립한것으로 그 뒤 배열들은 전부 스택에 넣어준다.

만약 else라면 하나만 넣어준다.

마지막으로 문자들을 합치고 앞에서부터 전체수 - 삭제된 수를 뺀 자릿수만큼 리턴해준다.

앞에서부터 자릿수만큼 리턴해주는 이유는 만약 987654321이란 숫자가 들어오고 2개 삭제를 한다치면 순차적으로 스택에 다 들어오기때문에 꼭 걸려줘야 하는 예외처리이다.

 

 

[참고자료]

programmers.co.kr/learn/courses/30/lessons/42883