LeetCode 393. UTF-8 Validation

파이썬 알고리즘 인터뷰 73번(리트코드 393번) UTF-8 Validation
https://leetcode.com/problems/utf-8-validation/

나의 풀이

class Solution:
    def validUtf8(self, data: List[int]) -> bool:
        memo = {2:0, 3:0, 4:0}
        curr = 0
        for num in data:
            if num // (2 ** 7) == 0: # 0xxxxxxx
                if memo[2] > 0 or memo[3] > 0 or memo[4] > 0:
                    return False
                continue
            else: # 1xxxxxxx
                num = num % (2 ** 7)
                if num // (2 ** 6) == 0: # 10xxxxxx
                    if curr == 0:
                        return False
                    else:
                        memo[curr] += 1
                        if memo[curr] == curr:
                            memo[curr] = 0
                            curr = 0
                else: ## 11xxxxxx
                    num = num % (2 ** 6)
                    if num //(2 ** 5) == 0: # 110xxxxx
                        if curr == 0:
                            memo[2] = 1
                            curr = 2
                        else:
                            return False
                    else: # 111xxxxx
                        num = num % (2 ** 5)
                        if num // (2 ** 4) == 0: # 1110xxxx
                            if curr == 0:
                                memo[3] = 1
                                curr = 3
                            else:
                                return False
                        else: # 1111xxxx
                            num = num % (2 ** 4)
                            if num // (2 ** 3) == 0: # 11110xxx
                                if curr == 0:
                                    memo[4] = 1
                                    curr = 4
                                else:
                                    return False
                            else:
                                return False
        if memo[2] > 0 or memo[3] > 0 or memo[4] > 0:
            return False
        return True

• 아직 비트 연산자, 파이썬에서 2진수 표현 등이 익숙하지 않았다.
• 처음에 비트 연산자 <<, >> 를 이용하여 풀이하려 시도했으나, 비교할 때 0b11110처럼 이진법으로 표현한 수와 비교할 생각을 못했다.
• 0b11110라고 쓰면 수가 아닌 문자열이 나온다고 착각했었기 때문이다.
• bin(10)이라고 입력하면 문자열로 출력이 되는데 이것과 착각했다.
• 파이썬의 진법 표현에 익숙해져야겠다.

다른 풀이1

class Solution:
    def validUtf8(self, data: List[int]) -> bool:
        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

• start는 부모 함수의 immutable변수인데 중첩 함수에서 읽을 수가 있구나. 다만 변경은 안된다.

다른 풀이2

class Solution:
    def validUtf8(self, data: List[int]) -> bool:
        count = 0
        
        for num in data:
            if count == 0:
                if (num >> 5) == 0b110:
                    count = 1
                elif (num >> 4) == 0b1110:
                    count = 2
                elif (num >> 3) == 0b11110:
                    count = 3
                elif (num >> 7) != 0:
                    return False
            else:
                if (num >> 6) != 0b10:
                    return False
                count -= 1
        
        return count == 0

배운 점

• 파이썬의 비트 연산자, 진법 표현에 익숙해지자.
• 부모 함수의 변수를 호출할 수 있다. 다만 값을 변경하는 것은 immutable 변수만 가능하다.