1. 문제 소개

717. 1-bit and 2-bit Characters

2. 나의 풀이

처음봤을 때에는 문제를 잘 이해하지 못했는데, 알고보니 쉬운 문제였다.
배열을 한 번 쭉 순회하며 되는 문제였다.
시간복잡도는 $O(n)$이다.

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        if bits[-1] == 1:                # 마지막 비트가 1이면, 1-bit 문자(0)로 끝날 수 없으므로 바로 False
            return False

        n = len(bits)                    # 비트 배열의 길이
        i = 0                            # 현재 읽고 있는 인덱스(포인터)
        scan = []                        # 파싱된 문자들을 저장할 리스트 (0, 10, 11 형태로 저장)

        while i < n:                     # 비트 스트림 전체를 왼쪽에서 오른쪽으로 한 번 순회
            if bits[i] == 1:             # 현재 비트가 1이면, 반드시 2-bit 문자(10 또는 11)의 시작
                scan.append(bits[i] * 10 + bits[i+1])
                # 예: bits[i]=1, bits[i+1]=0 → 10, bits[i+1]=1 → 11 형태로 정수로 저장
                i += 2                   # 2비트를 하나의 문자로 소비했으므로 인덱스를 두 칸 전진
            else:
                scan.append(bits[i])     # bits[i]가 0이면 1-bit 문자이므로 그대로 0을 저장
                i += 1                   # 한 비트만 사용했으므로 한 칸 전진
        
        # print(scan)                    # 디버깅용: 파싱된 문자 리스트(0, 10, 11)를 확인하기 위한 출력 (주석 처리)

        return True if scan[-1] == 0 else False
        # 파싱된 문자들 중 마지막 문자가 0이면 → 마지막 문자가 1-bit 문자(0)이므로 True
        # 마지막 문자가 10 또는 11이면 → 마지막 비트는 2-bit 문자에 포함된 것이므로 False

3. 다른 풀이

똑같은 시간복잡도이지만 공간복잡도를 줄인 풀이이다.
비트의 길이만큼 진행해서 배열의 길이와 딱 1만큼 차이가 나는 경우 정답이다.

class Solution(object):
    def isOneBitCharacter(self, bits):
        i = 0                                    # 비트 스트림을 왼쪽부터 읽어갈 포인터

        while i < len(bits) - 1:                 # 마지막 비트 직전까지만 확인
            # bits[i]가 0이면 → 1-bit 문자이므로 i += 1
            # bits[i]가 1이면 → 2-bit 문자(10 또는 11)이므로 i += 2
            # 이를 통합한 표현이 i += bits[i] + 1
            i += bits[i] + 1

        # 루프 종료 후 i가 정확히 len(bits) - 1이면,
        # 마지막 비트가 단독으로 1-bit 문자(0)로 처리된 것
        # i가 그보다 크면 → 마지막 비트는 2-bit 문자 내부에 포함된 것
        return i == len(bits) - 1

4. 결론

오늘도 내 힘으로 풀어서 좋다.