Codility Lesson 1 Iteration

코딩테스트를 위해 오늘 부터 알고리즘 문제를 풀어보려 한다. 우선 Codility 사이트의 테스트 문제들을 풀어봤는데 생각보다 어렵다;;;
테스트 문제는 완료하지도 못한채로 제출을 해버렸다..

오늘부터 Codility 사이트의 Lession 문제들을 차근차근 풀어보려 한다. 더불어 예전에 조금 깨작? 거렸던 Cordwars도 풀어볼 것이다.
개인적으로 알고리즘 문제를 풀 땐 연습장에 직접 써보면서 풀어가는데, 채용시 코테에서 연습장을 쓸 수 있을지는 의문이다. 이때문에 컴퓨터 상에서 풀어보는 연습도 필요하다.
그리고 Codility의 경우 run task를 할 경우 테스트 케이스의 결과만 보여주기 때문에 내부에서 어떻게 돌아가는지 파악하기 어렵다…
그래서 찾아낸 방법은 jsFiddle로 코드를 작성하면서 컴파일을 돌리고, 결과 코드를 복붙! 하면 좀 더 시간을 단축 시킬 수 있을 것 같다.
오늘 부터 한 문제씩 업로드 하고 내가 풀었던 코드들도 같이 올릴 것이다.

문제

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps.

Write a function:

function solution(N);

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn’t contain a binary gap.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation ‘100000’ and thus no binary gaps.

Assume that:

N is an integer within the range [1..2,147,483,647].
Complexity:

expected worst-case time complexity is O(log(N));
expected worst-case space complexity is O(1).

문제해설 : 주어진 Integer N이 있고, 이를 이진수로 변환하였을 때 1과 1사이의 0의 갯수를 gap이라 한다.
예를 들어 9는 이진수로 1001이며 gap의 길이는 2가 된다.
숫자 529의 경우 이진수로 1000010001이며 이 경우에는 gap이 4와 3이다.
function solution(N);
함수 solution에서 N이 파라미터로 주어졌을 때 가장 긴 gap값을 찾아라.
단 gap이 존재하지 않을 경우 0을 리턴해야 한다. 예를들어 N = 32인 경우 이진수로 100000이며 이때의 gap은 0이다.
N은 [1..2,147,483,647]의 범위 값을 가진다.
복잡도 :
최악의 시간 복잡도 케이스는 O(log(N)) 이다.
최악의 공간 복잡도 케이스는 O(1) 이다.

  • js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function solution(N) {
  var binaryValue = (N >>> 0).toString(2);
  var innerCount = 0;
  var gap = 0;

  var i;
  for(i=1; i< binaryValue.length; i++) {
    if(binaryValue[i] == 0) {
      innerCount++;
    } else {
      if(innerCount > gap) {
	      gap = innerCount;
      }
	  innerCount = 0;
    }
  }
  return gap;
}

답안 해설

우선 주어진 값을 이진값으로 변환하기 위해 toString()을 사용하였다. 이때 인자로 들어간 ‘2’ 값은 optional인데 2일 경우 binary 문자열로 리턴해준다.

이렇게 변환된 binary문자열은 (해당 문자열의 길이 - 1) 만큼 반복문을 돌게된다.

각 인덱스 순서대로 값을 확인하면서, 값이 0일 경우, 반복되는 0의 갯수를 count하는
innerCount라는 값이 증가하게 되고 1일 경우 현재의 innerCount와 이전의 gap을 비교하여 현재의 innerCount, 즉 새로 count 된 gap이 클경우 이를 gap에 할당한다.

이후 innerCount는 초기화 되며 다시 gap을 찾기위해 count 한다.

실행결과

Lesson 1 Codility ResultLesson 1 Codility Result