[알고리즘 문제풀이] Codility - BinaryGap

yourjin·2022년 8월 10일

iterations 알고리즘

알고리즘 문제풀이

목록 보기

25/28

➕ 오늘 푼 문제

Codility - BinaryGap

➕ 아이디어

이진수로 변환한 숫자에서 가장 긴 연속된 0의 길이를 구하는 문제이다.

start 와 end 변수를 통해 양쪽 끝에 있는 1의 위치를 담고 있는 변수이다.
start, end 를 -1로 초기화하고, start 가 -1이라면 제일 처음 만나는 1이기 때문에, 이 인덱스 값을 start의 값으로 바꿔준다.
그 이후에 만나는 1의 인덱스 값은 end 의 값으로 바꿔주고 사이에 있는 0의 개수를 계산한다. 계산이 끝난 후에는 end 값을 start 값으로 바꿔준다.
이 과정을 숫자가 끝날 때까지 반복했을 때 가장 큰 값이 정답이다.

➕ Java 코드

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int N) {
        // write your code in Java SE 8
        String binaryString = Integer.toBinaryString(N);
        int count = 0;
        int start = -1, end = -1;

        for(int i=0; i<binaryString.length(); i++){
            if(binaryString.charAt(i) == '1'){
                if(start == -1){
                    start = i;
                }else{
                    end = i;
                    count = Math.max(count, end-start-1);
                    start = i;
                }
            }
        }

        return count;
    }
}