[Coding Test] 1. Binary Gap

1. Binary Gap 문제

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:

class Solution { public int solution(int N); }

위 문제를 살펴보면, 우선 정수를 binary number, 즉 2진법으로 변환 후, 1 과 1 사이 “0”의 갯수를 세는 간단한 문제입니다. 조금 tricky할 수 있는 부분은, “0”의 갯수를 세다는 도중 1을 만났을 시, 다시 “0”의 갯수를 0부터 세야 하는 것입니다.

2. 풀이

그럼 바로 풀이 과정을 살펴보겠습니다.

import java.util.*;

class Solution {
    public int solution(int N) {
        // Implement your solution here
        int increment = 0;
        boolean swit = false;
        int max = 0;
        int mod = 0;

        while(N > 0) {
            mod = N%2;
            
            if(swit && mod == 0) {
                increment++;
            }

            if(mod == 1 && swit) {
                swit = false;
                increment = 0;
            }

            if(mod == 1 && !swit) {
                swit = true;
            }

            if(increment > max) max= increment;
            N = N/2;
        }
        return max;
    }
}

저의 경우에는, N의 2진법을 mod와 divide를 통해 구하는 동시에 “0”의 갯수를 구해줬습니다.

아래 조건식을 이용해 숫자를 언제 세고, 세지 말아야 할지 정의를 내려주었습니다 :

• 스윗치(swit)의 변수가 참이며 mod가 0일때만 increment를 증가시켜줍니다.
  
  
• mod가 1이고 스윗치가 불일때 스윗치 변수를 true로 변경해줍니다.
  
  
• mod가 1이고 스윗치 변수가 참일때는 “0”의 갯수를 세다 1을 만났다는 뜻이므로 스윗치를 off 해주고, increment를 0로 초기화 시켜줍니다.

마치며

물론 toBinaryString() 및 substring과 같은 함수를 사용하면 더욱 간편하고 심플하게 코드를 짤 수 있습니다. 다만, 대부분의 코딩 테스트에서의 심사 기준은 얼마나 함수를 사용하지 않고 문제를 해결하느냐로 합격 불합격이 정해질 수 있습니다. 위 코드는 참고만 하시되, 더욱 간편한 방법으로 문제 푸는 방법을 생각해보시는 걸 추천 드립니다.