Leetcode 를 풀어 보았다.

751. IP to CIDR

IP 주소가 주어지면, 이를 정수로 만든 다음 연속한 n개의 정수만을 커버하는 CIDR 의 최소 길이 배열을 찾으면 된다.

CIDR 이란, IP 주소 뒤에 비트 인덱스가 있어 이 비트 이후로는 어떤 숫자든 올 수 있기 때문에 여러 개의 IP 주소를 커버할 수 있다.

편의를 위해 아래 메소드를 생성했다.

func ipToNum(_ ip: String) -> Int {
    ip.split(separator: ".").compactMap { Int($0) }.reduce(into: 0) { r, c in
        r = r * 256 + c
    }
}

func bit(_ x: Int) -> Int {
    x & -x
}

func log(_ x: Int) -> Int {
    Int(log2(Double(x)))
}

func CIDR(_ num: Int, _ k: Int) -> String {
    [num/(256*256*256) % 256,
     num/(256*256) % 256
     num/256 % 256,
     um%256].map { "\($0)" }.joined(separator: ".") + "/\(k)"
}

ipToNum : ip 주소를 정수로 변환
bit : least significant bit 의 크기
log : Log2 값
CIDR : 정수와 비트 인덱스에 해당하는 CIDR 문자열로 변환

풀이는 그리디 알고리즘을 사용하면 된다. LSB 만큼 더했을 때 n 이 남아있는 경우 CIDR 에 해당한다.

func ipToCIDR(_ ip: String, _ n: Int) -> [String] {
    var num = ipToNum(ip), n = n, res = [String]()
    
    while n > 0 {
        var b = bit(num) > 0 ? bit(num) : Int(pow(2.0, Double(log(n))))
        while b > n {
            b = b / 2
        }
        res.append(CIDR(num, 32 - log(b)))
        num += b
        n -= b
    }
    
    return res
}

0.0.0.0 이 주어진 경우 bit(0) = 0 이기 때문에 무한 루프를 돌게 되고,
이를 위해 Int(log2(num)) 만큼 강제 전진 해주는 과정이 필요하다.