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

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

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

 

문자열로 주어진 수에서 순서를 유지한 상태로 k개 만큼 제거하여 얻을 수 있는 수 중 가장 큰 수를 만들고자 하는 문제. 

 

즉 1324에서 2개를 제외해서 가장 큰 수를 만든다면 34가 된다.

 

왜냐? 만들 수 있는 수가 13, 12, 14, 32, 34, 24뿐이기에 이 중에 최대는 34가 된다. 

자 여기까지 보면 brute-force인 것 같고, 조합을 구해서 최댓값을 구하면 문제가 풀릴 것 만 같다. 

 

하지만 문제의 제한 조건을 보면 주어지는 숫자는 1이상 1,000,000미만의 수이다. 즉 brute-force나 조합으로 풀기에는 경우의 수가 너무 많아서 시간효율적이지 못하다! 그렇기에 문제의 카테고리가 그리디 인 것!

 

그렇다면 어떻게 문제를 접근해야 할까?

 

가장 큰 수를 만들기 위해서는 가장 앞자리의 숫자가 커야하는 것은 기본적인 부분이다. 

이를 위해 값들을 비교해가며 Stack에 쌓고, 삭제하고를 반복하며 최댓값을 얻을 수 있었다. 

 

• result(Stack)의 마지막 값(last)와 다음에 들어올 number의 수를 비교한다.
  • result가 비어있다면 number의 가장 앞의 값 그냥 추가! index도 1 증가! 
  • last가 들어올 수보다 작다면 last를 제거해준다(result.removeLast()) 
    
    • 삭제 count += 1
  • last가 들어올 수 보다 크거나 같다면, 들어올 수를 그대로 쌓아준다. 
    • 다음 원소 선택을 위해 index값 += 1

그림으로 한 번 이해해보자.

작동 원리

위에 언급한 조건에 맞게 진행되는 것을 볼 수 있다. 

다만 이 경우는 count가 k와 같아지는 조건에 걸리는 경우이며, 

idx가 원 배열을 넘어서려고 하는 시점에서도 결과를 얻어내지 못하는 경우가 있을 수 있다. 

 

예를 들어 Number가 "1000"이라고 할 때 위 조건대로 실행하게 되면 최종적으로 얻게 되는 값은 다음과 같다. 

 

result = "1000", count = 0, idx = 4

 

배열을 다 돌았는데도 답이 나오지 않았다는 것은 위 방법이 통하지 않았다는 것이기에 뒤에서 부터 k만큼 차례대로 제거해주면 된다. 

즉 k=1인 경우 1000 > 100이 가장 큰 수가 되는 것이다. 

 

코드로 가보자!

 

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    // index로 접근하기 위해 하나씩 나눠준다. 
    let numb = number.map { String($0) }
    // 결과를 담을 배열
    var result = [String]()
    // 총 삭제 횟수 카운트
    var count = 0
    // 현재 뽑을 인덱스 
    var idx = 0
    
    // 삭제 카운트 < 가능 삭제 횟수 && 인덱스 < 배열의 총 길이
    while count < k && idx < numb.count{
        // last가 없을 경우 현재 값(numb[idx]) 추가, idx += 1 후 다음 원소로
        // 옵셔널 바인딩 
        guard let last = result.last else {
            result.append(numb[idx])
            idx += 1
            continue
        }
        
        // 선택한 수가 last보다 클 경우 last는 삭제, 삭제 카운트 += 1
        // 현재 값이 더 크다면 last값을 지워 전체 값을 더 크게 만들어 줄 수 있음 
        if last < numb[idx] {
            result.removeLast()
            count += 1
            continue
        } else {
            // last가 선택한 수 보다 크거나 같을 경우 result에 추가 
            result.append(numb[idx])
            idx += 1
        }
    }    
    
    // "1000"의 케이스 > "100"이 됨 
    // 배열을 다 돌았으나 값을 찾지 못한 경우이기에, 뒤에서부터 k만큼 제거해준다. 
    if idx == numb.count {
        return result[0..<result.count - k].joined()
    }
    
    // 삭제를 알맞게 다 한 경우, 나머지 숫자들 그냥 이어붙이기
    if count == k {
        result += numb[idx...]
    }

    // 위 두 경우(idx == numb.count와 count == k)는 겹치는 일이 없음 무조건 하나의 조건에만 해당 
    return result.joined()
}

 

우선적으로는 위 조건대로 돌기는 하나, 그럼에도 결과를 얻지 못하는 경우 까지 생각해줘야 하는 문제이다. 

(예외 케이스를 잘 생각했어야...)

 

또한 제한 조건 상 숫자가 큰 편이기에 조금조금씩 문제를 풀어나가는 방법이 효율적이다. 

앞으로도 문제 상 입력 범위가 너무 크다면 문제를 쪼개서 해결할 수 있는 방법으로 고안해야 할 것 같다. 

 

끄읕