[Algorithm] 4주차 1번 문제

✅ 문제

---

양수 N을 이진법으로 바꿨을 때, 연속으로 이어지는 0의 갯수가 가장 큰 값을 반환하는 프로그램을 작성해주세요.

• 이어지는 0은 1과 1사이에 있는 것을 의미합니다.

• 이런 것을 binary gap 이라고 합니다.

예시입니다:

input: 9
output: 2
설명: 9의 이진수는 1001 입니다. 
1과 1사이에 있는 0은 2 이므로, 2를 return

input: 529
output: 4
설명: 529의 이진수는 1000010001 입니다. 
1과 1사이에 있는 연속된 0의 수는 4와 3입니다.
이 중 큰 값은 4이므로 4를 return

input: 20
output: 1
설명: 20의 이진수는 10100 입니다. 
1과 1사이에 있는 연속된 0의 수는 1 뿐입니다.
(뒤에 있는 0은 1사이에 있는 것이 아니므로)

input: 15
output: 0
설명: 15의 이진수는 1111 입니다. 
1과 1사이에 있는 0이 없으므로 0을 return

input: 32
output: 0
설명: 32의 이진수는 100000 입니다. 
1과 1사이에 있는 0이 없으므로 0을 return

📌풀이

---

문제 이해를 하면 다음과 같다.

#1 우선 인자로 받는 양수 n을 이진법으로 바꿉니다.

• bin() 메서드를 활용하여 이진수로 바로 변환하기.
• 반복문을 통해 몫과 나머지를 활용하여 이진수로 바로 변환하기.

#2 이진수로 바뀐 문자열을 순회하면서 1일 때는 0값을, 0일 때는 개수를 하나씩 늘려줍니다.

• 문자열을 순회하면서 1일 때는 0을 배열에 넣어줍니다.
• 0을 만난다면 1씩 변수에 증가시켜주고, 다시 1을 만난다면 0의 개수만큼 늘어난 변수를 배열에 넣어줍니다.

코드를 통해 알아보겠습니다.

1. bin() 메서드를 활용한 풀이 방법

def solution(N):
  	result = []
  	count = 0
 	
    #1
  	bi_num = bin(N)[2:]
   
    #2
  	for i in bi_num:
   		if i == "1":
      		result.append(count)
      		count = 0
    	else :
      		count += 1
      
  	return max(result)

bin()을 통해 이진수로 변환한 값은 0b#### 등과 같은 문자열로 바뀝니다.

2. 반복문을 활용한 풀이 방법

def solution(N):
  	bi_nums = []
  	result = []
	count = 0
  	
    #1
  	while True :
    	if N // 2 == 0 :
      		bi_nums.append(N % 2)
      		break
    	else :
      		bi_nums.append(N % 2)
      		N = N // 2
    
    #2
  	for i in bi_nums[::-1]:
    	if i == 1 :
      		result.append(count)
      		count = 0
    	else :
      		count += 1
  
  	return max(result)    

while 문을 통해 인자로 받는 N의 나머지를 새로운 배열에 넣어 이진수로 변환하는 방법을 사용했습니다.

while문이 한번씩 끝날 때마다 N은 2로 나눈 몫으로 새로 업데이트를 해주었습니다.

1 사이의 0을 세는 방법은 위의 코드와 동일합니다.