(1) 코딜리티 - binaryGap

코딜리티 첫번째 문제 : binaryGap

BinaryGap coding task - Learn to Code - Codility

1) 정수를 2진법으로 치환하고,
2) 2진법에서 1과 1사이의 거리가 가장 긴 구간을 찾아서 그 거리를 리턴하라는 문제.

 

알고리즘 문제를 푸는건 왜 이렇게 어려운건지 잘 모르겠다...ㅠㅠ

검색 안 해보고 내가 머리 끙끙 싸매서 풀어보려고 했는데, 2진법 변환부터 막혔다.

처음에 생각한 방법은, n을 2로 나눈 나머지를 임의의 배열에다가 담는 과정을 n / 2가 0이 될 때까지 반복하면, 임의의 배열에 0과 1로만 이루어진 2진법 숫자들이 모일 것 같았는데... 너무나 허접했던 논리 탓인지 저렇게는 2진법이 안 만들어지더라..ㅠㅠ

 

한 20-30분 싸매다가 검색해보니 toString(2) 메소드를 사용하면 2진법으로 변환해서 한다고 하던데...

저번 바닐라 코딩 1회차 피드백 받으러 갔을 때, Ken님이 내가 알고리즘 푼 것 보고 말씀하시길, 최대한 sort 메소드를 사용하지 말고, 만약 사용하고 싶으면 내가 함수를 만들어서 쓰라고 하셨었다.

 

지금 단계에서는 쉬운 방법으로 풀어내기 보다는, 어떻게 풀 것인지 그 로직과 알고리즘을 구현하는데 초점을 맞추라는 의미로 이해했기 때문에.. toString(2)로 쉽게 푸는 것 말고 알고리즘을 짜서 2진법을 만드는 방법을 추가로 시도해보려고 한다.

어쨌든 그렇게 2진법 수를 구한 후, 2진법 숫자에서 1이 등장할 때마다 그 때의 index를 어디엔가 담아 놓은 후, 그 index들 사이의 거리를 빼서 가장 큰 것을 구하게 했다.

 

많이 허접한 첫번째 풀이는 아래와 같다.

다시 풀어보고 업데이트 할 것이다.

 

1. 2019년 8월 29일(목) 21시 22분에 푼 1번 풀이

function solution(n) {
    const binary = n.toString(2);
    let arr = [];
    for (let i = 0; i < binary.length; i++) {
        if (binary[i] === '1') {
            arr.push(i);
        }
    }
    
    let biggest = 0;
    for (let j = 0; j < arr.length; j++) {
        if (arr[j+1] - arr[j] -1 > biggest) {
            biggest = arr[j+1] - arr[j] - 1;
        }
    }
    
    return biggest;
}

solution(9);