[파이썬 알고리즘 인터뷰][비트연산] UTF-8 검증

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

입력값이 UTF-8 문자열인지 검증

 

책에서 구현된 코드

class Solution:
    def validUtf8(self, data: List[int]) -> bool:
        # 문자 바이트 만큼 10으로 시작 판별
        def check(size):
            for i in range(start + 1, start + size + 1):
                if i >= len(data) or (data[i] >> 6) != 0b10:
                    return False
            return True

        start = 0
        while start < len(data):
            # 첫 바이트 기준 총 문자 바이트 판별
            first = data[start]
            if (first >> 3) == 0b11110 and check(3):
                start += 4
            elif (first >> 4) == 0b1110 and check(2):
                start += 3
            elif (first >> 5) == 0b110 and check(1):
                start += 2
            elif (first >> 7) == 0:
                start += 1
            else:
                return False
        return True

 

기억해야할 기법

• 8개 비트중 앞자리 3개를 확인하고 싶으면, num >> 5으로 확인하기

 

내가 구현한 코드

class Solution:
    def validUtf8(self, data: List[int]) -> bool:
        def get_len(num: int) -> int:
            cnt = 0
            mask = 0b10000000
            l = num & mask
            while l:
                l = num & (mask >> cnt)
                cnt += 1
            return cnt

        mask = 0xFF
        check = [
            [ 0b10000000 ],
            [], [],
            [ 0b11100000, 0b11000000 ],
            [ 0b11110000, 0b11000000, 0b11000000 ],
            [ 0b11111000, 0b11000000, 0b11000000, 0b11000000],
            [], [], [], []]

        idx = 0
        while idx < len(data):
            head = data[idx]
            l = check[get_len(head)]
            if not len(l):
                return False
            for i, byte in enumerate(l):
                if len(data)-1 < i+idx or (data[i+idx] & byte) != mask & (byte << 1):
                    return False
            idx += len(l)
        return True

• 간단한 비트연산이 아니면 디버깅 없이 구현이 힘들 것 같다