C++로 구현하는 UTF-8 인코딩 유효성 검사 완벽 가이드

UTF-8 유효성 검사 문제란?

정수 리스트가 주어졌을 때, 해당 데이터가 유효한 UTF-8 인코딩인지 판별하는 문제입니다. 하나의 UTF-8 문자는 1바이트에서 4바이트 길이까지 가질 수 있으며, 각 문자는 다음과 같은 규칙을 따릅니다.

• 1바이트 문자: 첫 번째 비트는 0이며, 나머지 비트에 유니코드 코드 포인트가 저장됩니다.
• n바이트 문자(n ≥ 2): 첫 n개 비트는 모두 1이고, n+1번째 비트는 0입니다. 이어지는 n-1개의 바이트는 모두 최상위 2비트가 10으로 시작해야 합니다.

UTF-8 인코딩 규칙 정리

유니코드 문자의 값 범위에 따라 UTF-8 옥텟(octet) 시퀀스는 아래 표와 같이 결정됩니다.

예제로 이해하기

입력이 [197, 130, 1]이라고 가정해 보겠습니다. 이를 2진수로 표현하면 11000101 10000010 00000001이 됩니다.

• 첫 번째 바이트 11000101은 2바이트 문자의 시작(110xxxxx)을 의미합니다.
• 두 번째 바이트 10000010은 올바른 연속 바이트(10xxxxxx)입니다.
• 세 번째 바이트 00000001은 1바이트 문자(0xxxxxxx)입니다.

즉, 2바이트 문자 하나와 1바이트 문자 하나로 구성된 유효한 UTF-8 인코딩이므로 결과는 true가 됩니다.

알고리즘 접근 방법

이 문제는 비트 연산(bit manipulation)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 현재 처리 중인 문자가 몇 바이트인지 추적하는 카운터 변수를 유지하는 것입니다.

1. 카운터 변수 cnt를 0으로 초기화합니다.
2. 데이터 배열의 각 요소 x에 대해 다음을 반복합니다.
   • cnt가 0이면 새로운 문자의 시작을 의미하므로, 상위 비트를 검사하여 문자의 바이트 길이를 판별합니다.
     • x >> 5 == 0b110 → 2바이트 문자이므로 cnt = 1
     • x >> 4 == 0b1110 → 3바이트 문자이므로 cnt = 2
     • x >> 3 == 0b11110 → 4바이트 문자이므로 cnt = 3
     • x >> 7 != 0 → 1바이트 문자도 아닌 잘못된 시작 바이트이므로 false 반환
   • cnt가 0이 아니라면 현재 바이트는 연속 바이트여야 하므로, x >> 6 != 0b10이면 false 반환, 그렇지 않으면 cnt를 1 감소시킵니다.
3. 모든 바이트를 처리한 후 cnt가 0이면 true, 아니면 false를 반환합니다. (연속 바이트가 부족한 경우를 걸러냅니다.)

C++ 구현 예제

아래는 위 알고리즘을 C++로 구현한 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool validUtf8(vector<int>& data) {
        int cnt = 0;
        for(int i = 0; i <data.size(); i++){
            int x = data[i];
            if(!cnt){
                if((x >> 5) == 0b110){
                   cnt = 1;
                }
                else if((x >> 4) == 0b1110){
                   cnt = 2;
                }
                else if((x >> 3) == 0b11110){
                   cnt = 3;
                }
                else if((x >> 7) != 0) return false;
            } else {
                if((x >> 6) != 0b10) return false;
                cnt--;
            }
        }
        return cnt == 0;
    }
};
main(){
    Solution ob;
    vector<int> v = {197,130,1};
    cout << (ob.validUtf8(v));
}

실행 결과

입력:

[197,130,1]

출력:

1

출력값 1(true)은 입력 데이터가 유효한 UTF-8 인코딩임을 의미합니다.

마무리

이 문제의 시간 복잡도는 O(n), 공간 복잡도는 O(1)로, 데이터 배열을 한 번만 순회하면서 비트 시프트 연산으로 각 바이트의 역할을 판별하는 것이 핵심입니다. 비트 마스크나 정규표현식 등 다양한 방법으로도 풀 수 있지만, 카운터 기반의 비트 연산 접근법이 가장 직관적이고 효율적입니다.