[Algorithm] 큰 수 만들기

[hwangJi-dev]

💬 Idea

1. 처음에 조합이라는 생각보다는 큰 순서대로 문자열을 정렬한 후 k개를 제외한 자릿수만큼 return을 하는 문제인가? 라고 문제를 잘못 파악하여 시간이 너무 오래 걸리게 되었다.. 문제를 잘 읽자!!
2. ✅ 자릿수의 개념으로 접근하자.

   1. k개를 제외하고 조합가능한 마지막 자릿수까지 범위를 설정하여 for문을 돌며 가장 큰 수를 구하자.

      ex: 4177252841 → k 개를 제외하면 return되는 문자열은 6자리이다.

      1. 먼저 구해야할 자리는 십만 자리의 수이다.
      2. 이 때, 최상단 자리(십만 자리)의 수가 될 수 있는 범위는 0부터 4이다. (index 0 ~ index 4)
      3. 따라서 index 0부터 4까지 돌면서 최대로 큰 수를 뽑는다. (이 때, 7이 뽑히게 된다. → index 2)
      4. 해당 문제는 “조합”될 수 있는 가장 큰 수를 뽑는 문제이므로 이전 index의 숫자들은 고려할 필요가 없다. 따라서 최대로 큰 수의 다음 자리(+1)로 maxIndex를 옮겨준다.

      다음 자릿수가 될 수 있는 수 중 최대의 수를 뽑기 위해 a~d의 단계를 반복한다.

💬 풀이

func solution(_ number:String, _ k:Int) -> String {
    let number = Array(number).map{ String($0) }
    var maxIndex = 0
    var lastIndex = k
    var maxString = ""
    
    // [1️⃣] k개수만큼을 제외한 자릿수만큼 반복
    for _ in 0..<number.count - k {
        var maxNumber = "0"
        
        // [🔑 시간 단축 조건]
        // maxIndex와 lastIndex가 같지 않다면 큰 수를 찾아가며 돌지만
        if maxIndex != lastIndex {
            // [2️⃣] maxIndex부터 lastIndex까지 돌며 가장 큰 수 찾기
            for j in maxIndex...lastIndex {
                // [🔑 시간 단축 조건] 1의자리 수 중 가장 큰 수인 9라면 반복문을 다 돌지 않고 탈출
                if number[j] == "9" {
                    maxNumber = number[j]
                    maxIndex = j + 1
                    break
                } else if number[j] > maxNumber {
                    maxNumber = number[j]
                    maxIndex = j + 1
                }
            }
            
            // for문을 다 돌고나면
            // 비교범위 중 가장 큰 수를 찾았단 뜻이므로 maxString에 maxNumber 추가
            maxString += maxNumber
            
            // [비교 범위의 lastIndex 조건]
            // k는 제거하려는 개수이므로 한자리씩 늘려가며 비교범위를 정하기 위해
            // k에 maxString의 count를 더해준다.
            lastIndex = k + maxString.count
        } else {
            // [🔑 시간 단축 조건]
            // maxIndex와 lastIndex가 같다면
            // 남은 number 배열의 수를 모두 maxString에 append해주고 탈출한다.
            for i in maxIndex..<number.count {
                maxString += number[i]
            }
            break
        }
    }
    return maxString
}

소요시간 : 2시간 30분

💬 더 나은 방법?

swift에서 stack의 개념으로 접근하여 푼 코드들이 있는 것 같아서 다음에는 stack으로도 한번 풀어보고 싶다!

💬 알게된 점

• 시간 단축에 신경쓰자. 예외 케이스와 시간 단축 방법을 찾는 것도 중요한 능력인 것 같다.