이번 글에서는 특수한 두 종류의 문자를 다루는 문제를 Python으로 해결해 보겠습니다.
문제 정의
두 가지 특수 문자가 있다고 가정해 봅시다. 첫 번째 문자는 한 개의 비트 0으로 표현되고, 두 번째 문자는 두 개의 비트 10 또는 11로 표현됩니다.
여러 개의 비트로 구성된 문자열이 주어졌을 때, 이 문자열을 디코딩했을 경우 마지막 문자가 반드시 1비트 문자인지 확인해야 합니다. 단, 입력으로 주어지는 비트 문자열은 항상 0으로 끝난다는 조건이 있습니다.
예시
입력이 [1, 0, 0]이라면 출력은 True입니다. 이 배열을 디코딩하는 유일한 방법은 2비트 문자(10)와 1비트 문자(0)로 나누는 것이기 때문입니다. 따라서 마지막 문자는 1비트 문자가 됩니다.
풀이 접근 방식
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- bits 배열의 크기가 1보다 큰 동안 반복합니다.
- 배열의 첫 번째 요소를 current에 저장한 뒤, 해당 요소를 제거합니다.
- current가 1이라면, 이는 2비트 문자의 시작이므로 다음 요소도 함께 제거합니다.
- 반복 후 bits 배열이 비어 있다면 False를 반환합니다.
- 마지막으로 bits[0]이 0이면 True를, 그렇지 않으면 False를 반환합니다.
핵심 아이디어는 앞에서부터 순차적으로 비트를 소모하며 디코딩을 시뮬레이션하는 것입니다. 1을 만나면 반드시 뒤따르는 비트와 묶여 2비트 문자가 되므로, 마지막에 남은 비트가 0인지만 확인하면 됩니다.
구현 코드
아래 구현을 통해 더 자세히 이해해 보겠습니다.
class Solution: def isOneBitCharacter(self, bits): while len(bits) > 1: current = bits.pop(0) if current == 1: bits.pop(0) if len(bits) == 0: return False return bits[0] == 0 ob = Solution() print(ob.isOneBitCharacter([1,0,0]))
입력
[1,0,0]
출력
True
마무리
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)(입력 배열을 직접 수정하는 경우)입니다. 참고로 실제 코딩 테스트에서는 pop(0)이 O(n) 연산이므로 인덱스 포인터를 사용하는 방식이나 역방향 탐색 기법을 활용하면 더 효율적인 구현이 가능합니다.