Codility - Lesson 1 Iterations BinaryGap

알고리즘 공부를 너무 안한거 같아서 codility에서 하나씩 풀어보기로 했습니다. 우선 Lesson 1을 풀어보도록 하겠습니다. codility는 다양한 언어를 사용하여 주어진 문제에 대한 알고리즘을 작성하여 결과를 확인하는 사이트 입니다. 요즘 많은 회사에서 면접 coding test에서 사용하니 한번쯤 해보시면 좋을 것 같습니다.

 

Lesson 1 BinaryGap의 문제는 읽어 보면 N으로 들어온 숫자를 이진수로 변경했을 때 1과 1사이의 0값이 가장 큰 값을 반환하는 문제 입니다. 문제의 자세한 내용은 여기서 확인하시면 됩니다.

 

해결 code는 다음과 같습니다.

fun solution(N: Int): Int {
    // write your code in Kotlin
    var num = N
    var count = 0
    var ans = 0;
    var flag = false
    while(true){
     
        var remainder = num%2
        if(remainder == 1 && !flag){
            flag = true
        }else if(remainder == 1 && flag){
            flag = false
            if(ans < count){
                ans = count
            }
            count = 0
            if(num > 0 ){
                flag = true
            } 
        }else if(remainder == 0 && flag){
            count++
        }
        if(num == 0){
            break;
        }
        num = num/2
        
        
    }
    return ans;
}

remainder를 통하여 이진수를 변경할 때 그 값이 0 인지 1인지 구분 합니다. (10진수를 2진수로 만들 때 2로 나누어서 그 나머지 값으로 이진수를 만듭니다. ex) 9는 9/2 = 4...1 | 4/2= 2...0 | 2/2 = 1...0 | 1/2 = 0 ... 1 해서 나머지들로 맨 오른쪽 값부터 1001 이 됩니다.) 

그리고 remainder를 통하여 count의 시작 점과 끝나는 점을 확인 합니다. 최초의 1은 무조건 시작점입니다. 그래서 count를 하겠다는 flag 값을 true로 바꿔줍니다.

그다음에 remainder가 0일 경우 count를 1씩 올려 줍니다.

그리고 다시 remainder가 1이면 count를 종료하고(flag =false) 현재 ans의 값보다 count가 클 경우 ans에 count를 대입합니다. 그리고 이진수 변경이 끝났다면 종료를, 아니라면 그 1이 다시 시작 점이 되기 때 flag를 true로 변경합니다.

이진수 변경의 끝은 계속 2로 나누기를 하고 그 값이 0이 될 경우 더이상 나눌 수 없기 때문에 이진수 변경이 끝났다고 생각하시면 됩니다.

 

이진수 변경이 끝나면 break로 while을 종료하고, 그 ans값을 return 합니다.