Codility - BinaryGap 풀이

Lesson1. BinaryGap

안녕하세요!

자료구조와 알고리즘의 필요성에 대해서는 항상 느끼고 있었지만, 타 프로젝트나 시간이 없다는 등의 핑계로 미루기 일쑤였습니다.

그래서, 오늘부터 매일은 안 되더라도 적어도 일주일에 한 문제씩은 꼭 풀어보려 합니다.

같이 문제에 대해 탐구해보는 좋은 시간이 되었으면 좋겠습니다!

 

Question

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

BinaryGap coding task - Learn to Code - Codility

 

정리하자면, 정수의 2진 표현에서 1과 1사이에 있는 0의 가장 긴 순서를 찾는 문제입니다.

 

정수의 2진 표현이 100001과 같다면 4를 반환, 10001001과 같다면 3과 2중 더 큰 3을 반환, 10000과 같이 0이 1과 1사이에 있지 않다면 0을 반환하면 됩니다.

 

Answer

저는 주어진 정수가 이진수로 변환됐을 때, 1이 위치한 인덱스만 알면 해결이 훨씬 수월할 것 같아 다음과 같이 풀이했습니다.

 

1. 주어진 정수를 2진수로 변환하기

2. 변환된 2진수를 배열로 변환

3. 배열을 돌며, 1이 들어있으면 해당 인덱스를 배열 (스택) 에 push

4. 인덱스 배열의 길이 (length) 가 2보다 작으면, 0이 1과 1 사이에 있지 않다는 말이므로 0 반환

5. 이외의 경우에는, 인덱스 배열을 돌며 max 값을 찾음 (arr[index] - arr[index - 1])

6. 실제 0의 개수는 max보다 1 작으므로, 최종적으로 max - 1 반환

 

풀이 코드는 아래와 같습니다.

// 2진수 배열에서 1이 위치한 인덱스들의 배열을 반환하는 함수
function getIndicesArrOfOne(bin) {
  const binArr = bin.split('');
  const indicesArr = [];
    
  for (let i = 0, arrLeng = binArr.length; i < arrLeng; i++) {
    if (binArr[i] === '1') {
      indicesArr.push(i);
    }
  }
    
  return indicesArr;
}

// 메인
function solution(N) {
  const bin = N.toString(2);
  const indicesArr = getIndicesArrOfOne(bin);
    
  if (indicesArr.length < 2) {
    return 0;
  }
    
  let max = 0, result = 0;
    
  for (let i = 1, arrLeng = indicesArr.length; i < arrLeng; i++) {
    result = indicesArr[i] - indicesArr[i - 1];

    if (max < result) {
      max = result;
    }
  }
    
  return max - 1;
}

/*
- 주어진 N이 1183일 경우 -
bin = "10010011111"
indicesArr = [0, 3, 6, 7, 8, 9, 10]
for문을 돌면서, max 값은 3으로 변함

따라서, 실제 0의 개수는 max보다 1이 작은 2개
*/

결과 사진

 

The End

이상 BinaryGap에 대한 풀이였습니다.

다음 포스팅에는 Lesson2. CyclicRotation의 풀이에 대해 적어보려 합니다.

봐주셔서 감사합니다!