Algorithm / 숫자 짝꿍

1) 문제

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.

예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.)
두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요.

제한사항

• 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
• X, Y는 0으로 시작하지 않습니다.
• X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

2) 문제 풀이

func solution(_ X:String, _ Y:String) -> String {
    let x = X.map { Int(String($0)) ?? 0 }
    let y = Y.map { Int(String($0)) ?? 0 }
    
    var partner: [Int] = []
    
    for i in x where y.contains(i) {
        let count = y.filter { $0 == i }.count
        let partnerCount = partner.filter { $0 == i }.count
        
        if partnerCount < count {
            partner.append(i)
        }
    }
    
    partner.sort(by: >)
    
    if partner.isEmpty {
        return "-1"
    } else if partner.first == 0 {
        return "0"
    }
    
    return partner.map { String($0) }.joined()
}

결과

3) 코드 개선

문제점

1. x where y.contains(i)로 중복을 포함한 탐색을 수행하면서,
   매번 y.filter { $0 == i }.count를 계산 → 시간복잡도 매우 비효율적 (O(n²))

2. partner 배열에 중복을 컨트롤하면서 수동으로 추가
   → partner.filter { $0 == i }.count로 또 O(n) 반복 → 비효율

3. partner에 각 숫자를 한 번에 넣는 방식이 아니라 하나씩 append
   → 공통 개수만큼 정확히 추가하는 게 어려움

개선 방법

• 각 문자열의 숫자 등장 횟수를 세기 위해 Dictionary를 사용
• 공통으로 등장하는 숫자들 중, 최소 개수만큼 반복해서 결과에 추가
• 결과를 내림차순으로 정렬해서 큰 수부터 붙이기

func solution(_ X: String, _ Y: String) -> String {
    var xCount = [Int: Int]()
    var yCount = [Int: Int]()

    // 각 숫자의 등장 횟수를 기록
    for ch in X {
        let num = Int(String(ch))!
        xCount[num, default: 0] += 1
    }

    for ch in Y {
        let num = Int(String(ch))!
        yCount[num, default: 0] += 1
    }

    var result = [Int]()

    // 0~9 숫자 중 공통으로 등장한 숫자를 최소 개수만큼 결과에 추가
    for digit in (0...9).reversed() {
        if let xVal = xCount[digit], let yVal = yCount[digit] {
            let count = min(xVal, yVal)
            result += Array(repeating: digit, count: count)
        }
    }

    if result.isEmpty {
        return "-1"
    } else if result.first == 0 {
        return "0"
    }

    return result.map { String($0) }.joined()
}

결과