문제 링크

문제 풀이 아이디어

시간복잡도

weights의 길이가 최대 100,000입니다. 따라서 weights의 모든 사람을 짝지어서 (nC2) 짝꿍이 되는지 확인하는 방식으로 해서는 안되고 O(N) 안에 해결을 봐야 합니다.

Dictionary 활용

문제에서 궁금해하는 것은 어떤 사람이 누구와 짝지었느냐가 아닌 최종 짝꿍이 몇 쌍이냐는 것입니다. 따라서 몸무게가 같은 사람을 세서 Dictionary로 정리하고 문제에서 정해준 비율에 맞추어서 짝꿍이 될 수 있는지 확인하면 됩니다.

Double

Swift에서는 Int를 사용해서 나눗셈을 하면 자동으로 소수점 이하는 버립니다. 따라서 정확한 비율을 구하기 위해서는 dictionary의 key를 Int가 아닌 Double로 해야합니다.

코드

func solution(_ weights:[Int]) -> Int64 {
    
    // 몸무게 - 사람수로 dict에 등록
        // 나눗셈을 정확하게 해야하므로 버림하는 Int가 아니라 Double로
    var dict = [Double:Int]()
    
    for weight in weights {
        dict[Double(weight), default: 0] += 1
    }
    
    var ans = 0
    
    // 비율이 1:1, 2:3, 2:4, 3:4인 사람들끼리 짝꿍
    for key in dict.keys {
        // 비율 1:1 = 몸무게가 같음 = key의 value가 1 이상
        if dict[key]! > 1 {
            // 서로 짝꿍 = nC2
            ans += dict[key]! * (dict[key]! - 1) / 2
        }
        
        // 2/3인 사람들과 짝꿍
        if dict[key * 2/3] != nil {
            ans += dict[key]! * dict[key * 2/3]!
        }
        
        // 2/3인 사람들과 짝꿍
        if dict[key * 2/4] != nil {
            ans += dict[key]! * dict[key * 2/4]!
        }
        
        // 2/3인 사람들과 짝꿍
        if dict[key * 3/4] != nil {
            ans += dict[key]! * dict[key * 3/4]!
        }
    }
    
    return Int64(ans)
}