[프로그래머스] 큰 수 만들기

 

▼ 문제 링크

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

 

처음에는 문제를 읽고 다음과 같이 단순한 과정을 거쳐 풀이를 시도했다.
1) k개의 숫자를 제거한 모든 조합의 숫자 구하기
2) 1)에서 구한 숫자 중에서 가장 큰 수 구하기

그러나, 이렇게 했더니 1, 11, 12번 테스트케이스 말고는 전부 시간 초과로 실패했다. 😢 

한참을 고민해 본 결과, 이건 내가 지금처럼 생각해서는 시간 초과를 해결할 수 없을 거라고 생각했고... 결국 구글링의 힘을 빌렸다. 😭

 

💡문제 해결 포인트
이 문제에서는 숫자의 순서가 뒤섞이지 않는다!

 

문제 내 설명에 이런 문장이 있다.

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

위 예시에서 49라던가 91같은 수는 나오지 않는다.
즉, n개의 수 중 k개를 제거하되, 그 순서는 유지한다는 뜻이다. 

앞자리 수와 뒷자리 수를 비교했을 때, 뒷자리 수가 더 크다면 앞자리 수를 제거하면 된다는 것이다.

 

전체 코드

import Foundation

func solution(_ number: String, _ k: Int) -> String {
    var numbers: [Character] = number.map({ $0 })
    var index = 0
    var delete = 0
    var stack: [Character] = []
    
    // 문제 자체가 숫자의 순서를 섞지 않고 중간중간 숫자만 제거하는 형태이므로
    // 삭제된 숫자가 k개가 되거나, numbers의 모든 숫자를 순회할 때까지 반복
    while delete < k && index < numbers.count {
        if let last = stack.last {
            // 새로운 index요소 값이 stack의 마지막 값보다 클 때
            if numbers[index] > last {
                // stack의 마지막 요소 제거
                stack.removeLast()
                // 삭제된 숫자 개수 1 추가
                delete += 1
                continue
            }
            
            stack.append(numbers[index])
            index += 1
        } else {
            // result가 빈 배열일 때는 index 요소 값 추가
            stack.append(numbers[index])
            index += 1
        }
    }
    
    // k개의 숫자를 삭제했으나, index가 numbers의 모든 요소를 순회하지 못했을 때
    // 결과값은 항상 numbers.count-k개여야 하므로
    // index이후의 요소들을 모두 추가해준다.
    if delete == k {
        stack.append(contentsOf: numbers[index...])
    }
    
    // index가 numbers의 모든 요소를 순회했으나, 아직 k개 만큼의 숫자를 삭제하지 못했을 때
    // 현재 stack에는 원래 목표보다 k-delete만큼 숫자가 더 들어가 있는 상태
    // 문제에서 제시한 조건은 요소를 앞에서부터 순차적으로 붙여서 숫자로 만들기 때문에
    // stack의 뒤에서 (k-delete)개를 빼준다.
    if index == numbers.count {
        stack = Array(stack[0..<number.count-(k-delete)])
    }
    
    return stack.reduce("", {"\($0)\($1)"})
}

while문 내부는 쉽다. stack 형태의 후입선출 형태를 띄는 배열을 만든다. 그리고 이 배열의 마지막 요소와 index가 가리키는 새 요소 중 더 작은 요소를 제거하고 더 큰 요소를 추가하면 된다.

여기서 중요한 건 while문의 조건이다.

"삭제된 숫자가 k개가 되거나, numbers의 모든 숫자를 순회할 때까지 반복"

두 조건 중 하나라도 충족하지 못하면 반복문을 멈춘다.
그리고 반복문이 끝난 뒤, 두 조건중 여전히 충족하는 조건이 있다면 이를 위해 배열을 추가하거나 삭제해줘야 한다.

 

이해를 돕기 위해 주석을 추가해뒀다.

아무리 모든 경우의 수를 헤아려야 한다고 하더라도 숫자의 순서가 바뀌지 않는다면 이런식으로도 생각할 수 있구나... 싶었다. 

 

※ 알고리즘 풀이는 이곳을 참고했습니다.

[프로그래머스] 탐욕법(Greedy) - 큰 수 만들기 (Swift 풀이)