codility는 모든 문제가 영문으로 나온다. 문제 풀이에 시간 제한이 있으므로 구글번역기를 돌리고 해석이 어색한 부분은 직접 독해하는게 좋은 방법이라고 생각한다.

문제

영문

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps.

Write a function:

public func solution(_ N : Int) -> Int

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..2,147,483,647].

한글

양의 정수 N 내의 Binary Gap은 N의 이진 표현에서 양쪽 끝에서 1로 둘러싸인 연속 0의 최대 개수입니다.

예를 들어, 숫자 9는 이진 표현 1001을 갖고 길이가 2인 Binary Gap을 포함합니다. 숫자 529는 이진 표현이 1000010001이고 두 개의 Binary Gap(길이 4 중 하나와 길이 3 중 하나)을 포함합니다. 숫자 20에는 이진 표현 10100이 있고 다음을 포함합니다. 길이가 1인 하나의 Binary Gap. 숫자 15는 이진 표현 1111을 가지며 Binary Gap이 없습니다. 숫자 32는 이진수 표현이 100000이고 Binary Gap이 없습니다.

함수 작성:

public func solution(_ N : Int) -> Int

양의 정수 N이 주어지면 가장 긴 Binary Gap의 길이를 반환합니다. N에 Binary Gap이 포함되지 않은 경우 함수는 0을 반환해야 합니다.

예를 들어, N = 1041이 주어지면 함수는 5를 반환해야 합니다. N은 이진 표현이 10000010001이고 가장 긴 이진 간격의 길이는 5이기 때문입니다. N = 32가 주어지면 함수는 0을 반환해야 합니다. N은 이진 표현이 '100000'이고 따라서 Binary Gap이 없습니다.

다음 가정에 대한 효율적인 알고리즘을 작성하십시오.

N은 [1..2,147,483,647] 범위의 정수입니다.

풀이

import Foundation


public func solution(_ N : Int) -> Int {
    let decimal: Int = N
    let binary: String = String(decimal, radix: 2)
    let binaryArray = Array(binary)
    var maxLength = 0
    var maxLengthCache = [0]
    var isZero = false
    var isChanged = false
    for x in 0...binaryArray.count-1 {
        if(binaryArray[x] == "1"){ /* 1일 때 */
            // 직전에 0이었을 때
            if(isZero && isChanged) {
                maxLengthCache.append(maxLength)
                maxLength = 0
                isChanged = false
            }
            
            isZero = false
            
        } else /* 0일 때 */ {
            // 직전에 1이었을 때
            if(!isZero) {
                isChanged = true
            }
            
            maxLength += 1
            isZero = true
        }
    }
    return maxLengthCache.max()!
} 

Test Case Result

임의로 제가 넣은 숫자입니다.

solution(1041)
// Result
10000010001 // binary
["1", "0", "0", "0", "0", "0", "1", "0", "0", "0", "1"] // binaryArray 
[0, 5, 3] // maxLengthCache

solution(1)
// Result
10000010001 // binary
["1", "0", "0", "0", "0", "0", "1", "0", "0", "0", "1"] // binaryArray 
[0, 5, 3] // maxLengthCache

solution(9)
// Result
1001 // binary
["1", "0", "0", "1"] // binaryArray 
[0, 2] // maxLengthCache

solution(657)
// Result
1010010001 // binary
["1", "0", "1", "0", "0", "1", "0", "0", "0", "1"] // binaryArray 
[0, 1, 2, 3] // maxLengthCache

solution(128)
// Result
10000000 // binary
["1", "0", "0", "0", "0", "0", "0", "0"] // binaryArray 
[0] // maxLengthCache