Code Kata#14 Binary Gap ***
정수를 2진수로 변환했을때 가장 긴 0의 연속길이를 찾는 알고리즘.
#문제
양수 N을 이진법으로 바꿨을 때, 연속으로 이어지는 0 중에서 가장 큰 값을 return해 주세요.
* 이어지는 0은 1과 1사이에 있는 것을 의미합니다.
* 1과 1사이에 있는 0을 binary gap 이라고 하겠습니다.--------------------------------------------------------------------input: 9
output: 2
설명: 9의 이진수는 1001 입니다.
1과 1사이에 있는 0은 2 이므로, 2를 return
--------------------------------------------------------------------
input: 529
output: 4
설명: 529의 이진수는 1000010001 입니다.
binary gap은 4와 3 두개가 있습니다.
이 중 큰 값은 4이므로 4를 return
--------------------------------------------------------------------
input: 20
output: 1
설명: 20의 이진수는 10100 입니다.
1과 1사이에 있는 연속된 0의 수는 1 뿐입니다.
(뒤에 있는 0은 1사이에 있는 것이 아니므로)
--------------------------------------------------------------------
input: 15
output: 0
설명: 15의 이진수는 1111 입니다.
binary gap이 없으므로 0을 return
--------------------------------------------------------------------
input: 32
output: 0
설명: 32의 이진수는 100000 입니다.
binary gap이 없으므로 0을 return
정수의 숫자가 주어지면, 2진법으로 바꾼다. 2진법표현식은 다음과 같다.
2진법 표현에서는 0과 1만 존재하는데 0이면 아무것도 없음을 의미하고 1이면 있음을 나타낸다. 111이라는 숫자가 있을경우 일의자리수, 십의자리수 백의자리수 세가지 모두 존재한다. 여기서 1은 1과 같다. 십의자리수 1은 2의 1승이다 백의자리수 1은 2의2승과 같다 . 일의자리수부터 십의자리수 ….등등 계속 증가할때마다 2의 n승을 해주면 된다.
위의 코드를 분석하면 다음과 같습니다.
1. binary라는 변수명을 만들어주고, 그 변수에는 N인자로 들어오는 숫자를 2진법으로 바꿔줍니다.( toString(2) )
2. binarySub에 ‘1’로끝나는 마지막 녀석을 찾는 값을 변수에 넣어줍니다. 첫번째는 무조건 1이 나올것이고. 마지막은 0이될수도있고 1이 될수도 있기 때문에 마지막으로 1이 나온애를 찾는것.
3. split으로 1을 나눠주고 map으로 그 값들을 분리. 그리고 max값을 추출!
또 다른 방법** 더 간단합니다.
- binary라는 변수 생성. 이 변수는 정수 N을 2진수로 바꿔준다.
- binaryArr 이라는 변수 생성. 이 변수는 변경된 2진수에서 1을 중심(제외)하고 분할. 즉 101001인경우 [‘’, ‘0’, ‘00’, ‘’ ]이 될것.
- for 반복문을 돌리는데 0부터 1씩 증가하지만, length -1까지만 돌린다. 그 이유는 마지막에 1이 있다면 binaryArr으로 변환될때 ‘’ 빈 값을 array에 포함시킬것이고 1이 없고 0이라면 binaryArr마지막에는 ‘’빈 스트링이 없을것이다. 즉 10100인 경우[‘’, ‘0’, ‘00’]이 되니까 마지막을 제외시켜야 함.
- binaryArr에서 가장큰 값 리턴을 하는데 마지막요소는 포함되지 않는다.
메서드를 살펴보겠습니다.
substr() 문자열을 추출하는 메서드
string.substr(start, length)
start로 시작위치를 정하고 length로 잘라낼 문자열의 길이를 정한다.lastIndexOf() 특정 문자열이 마지막에 나타는 위치를 반환하는 메서드이다. indexOf() 와의 차이점은 전자는 마지막, 후자는 처음으로 나타나는 위치를 찾는다는 것이다.
string.lastIndexOf(value, start) 특정 문자열이 마지막에 나타나는 위치를 반환하는 메서드이다.
value: 필수 요소. 찾으려는 문자열을 입력.
start: 선택 요소. 검색을 끝낼 인덱스 값. 입력하지 않으면 끝까지 검색.
대소문자를 구별하고, 찾는 문자열이 없는 경우 -1을 반환.split() 문자열 분할하는 메서드
string.split(separator, limit)
separator에는 분할의 기준을 넣습니다. 쉼표를 원하면 , 를 넣으면 됩니다.
limit으로 최대 분할 개수를 정할수 있고, 선택사항입니다. 넣지않으면 전체를 다 분할.tostring(2) 2진수를 변환
Math.max() 주어진 값 중에서 최댓값을 구함.
**********************************************************array.prototype.map() map메서드는 배열 내의 모든 요소 각각에 대하여 주어진 함수를 호출한 결과를 모아 새로운 배열을 반환합니다. 기존의 배열은 변하지 않는다.
