코딜리티 L1 BinaryGap 파이썬

2023-03-17

코딜리티 L1 BinaryGap 파이썬

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

무엇?

양의 정수를 이진수로 변환
변환된 이진수에서 1과 1사이에 위치한 0의 최대 길이를 구하는 문제

어떻게?

내 코드

1. N을 이진수로 변환 (bin() 메소드를 사용하면 문자열로 반환)
2. 이진수 반복문
   1. 0 갯수 세기
   2. 1을 만날 때만 최대값을 업데이트하기

def solution(N):
    binary_num = bin(N)[2:]
    max_gap = 0
    temp_gap = 0

    for i in binary_num:
        if i == 0:
            temp_gap += 1
        else:
            max_gap = max(temp_gap, max_gap)
            temp_gap = 0

    return max_gap

스택 사용

• 스택이 떠올라서 스택으로도 구현해보았다
• 여러모로 첫 번째 코드가 더 효율적이다
• 슈도코드

1. 이진수 변환
2. 이진수에 대해 반복문
   1. 원소가 1이고 스택이 비어 있지 않은 경우
      1. 스택에 담긴 1을 다시 만날때까지 스택 원소 pop
      2. 0의 개수 카운팅
      3. popping이 끝나면 최대 갭 업데이트
   2. 스택에 원소 추가

from collections import deque

def solution(N):
    stack = deque()
    gap = 0

    binary_num = bin(N)[2:]

    for i in binary_num:
        if i == '1' and len(stack) != 0:
            temp_gap = 0
            while stack[-1] != '1':
                stack.pop()
                temp_gap += 1
            gap = max(gap, temp_gap)
        stack.append(i)

    return gap