[코딜리티 문제] BinaryGap - 문자열

https://app.codility.com/programmers/lessons/1-iterations/

 

양의 정수 N 내의 이진 갭은 N의 이진 표현에서 양쪽 끝이 1로 둘러싸인 연속된 0의 최대 시퀀스입니다.
예를 들어, 숫자 9는 이진 표현 1001을 가지고 있으며 길이가 2인 이진 갭을 포함합니다. 숫자 529는 이진 표현 1000010001을 가지고 있으며 길이가 4인 하나와 길이가 3인 하나의 이진 갭을 포함합니다. 숫자 20은 이진 표현 10100을 가지고 있으며 길이가 1인 하나의 이진 갭을 포함합니다. 숫자 15는 이진 표현 1111을 가지고 있으며 이진 갭이 없습니다. 숫자 32는 이진 표현 100000을 가지고 있으며 이진 갭이 없습니다.

양의 정수 N이 주어지면 가장 긴 이진 갭의 길이를 반환합니다. N에 이진 갭이 없으면 함수는 0을 반환해야 합니다.
예를 들어, N = 1041일 때 함수는 5를 반환해야 합니다. N은 이진 표현 10000010001을 가지고 있고 가장 긴 이진 갭은 길이가 5이기 때문입니다. N = 32일 때 함수는 0을 반환해야 합니다. N은 이진 표현 '100000'을 가지고 있고 이진 갭이 없기 때문입니다.
다음 가정에 대한 효율적인 알고리즘을 작성하세요.

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

---

1. 아이디어

• 주어진 숫자 N을 이진수로 변환한다. → Integer.toString(N, 2)
• 연속된 0의 개수 중 최댓값을 찾되, 1로 둘러싸인 경우만 찾아야 한다.
• 0이 나오면, count++
• 1이 나오면, 현재 count 값을 비교하고 최댓값을 갱신

2. 시간복잡도

• 이진 변환: O(log N) (10진수 → 2진수 변환)
• 문자열 순회: O(log N) (2진수 길이는 O(log N))
• 총 시간복잡도: O(log N), 매우 빠름

class Solution {
    public int solution(int N) {
        String s = Integer.toString(N, 2); // 2진수 변환

        int max = 0; // 최대 Binary Gap
        int count = 0; // 현재 Binary Gap 길이

        for (char c : s.toCharArray()) {
            if (c == '0') {
                count++; // Binary Gap 증가
            } else {
                max = Math.max(max, count);
                count = 0; // // 카운트 초기화
            }
        }

        return max;
    }
}