[코테]코딜리티 - Binary Gap

문제

문제 요약

• int N이 매개변수로 주어짐
• N을 이진수로 변환했을 때, 1사이에 들어가 있는 연속된 0의 개수를 반환
• 다만, 여러번 반복 될 경우 가장 높은 값을 반환
• 1사이에 연속된 0이 없는 경우 0을 반환
• N의 범위는 1에서 Integer의 max value

문제 분석

나는 다음과 같은 단계를 통해 문제를 분석했다.

• 먼저 int N을 이진수로 변환한다.
• 이 때, int의 max_value인 2,147,483,647를 이진수로 변환하면 1이 31개가 나온다. 즉, 길이는 최대 31이다.
• 변환된 이진수를 char[]로 변환한다.
• 이후, 변환된 이진수 내에 1이 있는지 여부를 확인하고 없으면 0을 리턴.
• 1이 포함되어 있다면 char[]의 length만큼 반복문을 수행하며 1과 0을 찾아 카운트를 한다.
• 0이 시작되면 카운트를 1씩 증가시키고 1을 만나면 카운트를 이전 수치와 비교하여 더 높으면 대입한다.
• 반복문이 종료되고 최종적으로 남아있는 값을 리턴한다.

나와는 다르게 List를 이용 할 수도 있고, 문제를 분석하는 방법은 다를 수 있지만 한번 본인이 풀었던 것과 비교해보면 좋을 듯 하다.

슈도코드

N을 이진수로 변환한다.
변환된 이진수를 char[]에 저장한다.
계산된 값을 저장 할 int형 변수선언한다.

if(이진수에 1이 포함되어있지 않으면){
	0을 반환한다.
}

for(char[]의 길이만큼 반복한다){
	if(char[]의 인덱스가 0이면){
    	맥스값 1씩 증가시킨다.
    } else{
    	answer에 저장된 값이 현재 맥스값보다 작다면 answer에 맥스를 저장한다.
        맥스값을 초기화한다.
    }
}

answer을 반환한다.

구현코드

class Solution{
	public int solution(int N){
    	int answer = 0;
    	String binary = Integer.toBinaryString(N);
        char[] arr = binary.toCharArray();
        int max = 0;
        
        if(!binary.contains("1")){
        	return 0;
        }
        
        for(int i = 0; i < arr.length; i++){
        	if(arr[i] == '0') {
            	max++;
            } else{
            	if(answer < max) answer = max;
                max = 0;
            }
        }
        
        return answer;
    }
}

마무리

풀고나서 들었던 생각은 if(arr[i] == 0)max++; 이 부분에서 오류가 발생하지 않을까 싶다. 테스트 케이스는 다행스럽게도 0으로 시작해서 나중에 1이 나오는 케이스가 없었는데 생각해보면 000001011 이러한 형태로 테스트 케이스가 나온다면 0이 5개가 계산이 된 상태에서 1을 만나 max가 answer에 저장되는 상황이 발생한다. 이 부분은 코드를 개선 할 필요가 있겠다는 생각을 했다.