본문 바로가기

Programming/BOJ

BOJ 2680 · QR


알고리즘 분류 : 시뮬레이션, 문자열 처리  


이 문제는 최소 사이즈(21*21)의 QR 코드를 디코딩하는 문제다. 구현보다 문제 이해가 어려운 문제다. 인코딩된 16진수 코드를 원래 정보로 복원해야 한다. 문자열로 처리하여 다소 무식하게 구현했다.


  • 헥스 코드를 바이너리 코드로 변환한다.
  • 바이너리 코드를 앞에서부터 순서대로 읽으면서, 모드 비트(Mode Bits)와 카운트 비트(Count Bits)를 먼저 처리한다.
  • 숫자(Numeric)인 경우, 2진수를 10진수로 변환한다.
  • 숫자/문자(Alphanumeric)인 경우, 별도의 알파뉴메릭 배열을 만들어서 변환한다.
  • 8비트 문자(8 bit Byte) 또는 한자(Kanji)인 경우, 아스키 문자로 변환하거나 아스키 범위를 벗어나면 숫자로 출력한다.
  • 종료(Termination)인 경우, 바로 종료한다.




C++ 소스코드


#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int length;
string ans, s, bs;
string alphanum = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:";
string binary[] = {"0000", "0001", "0010", "0011", "0100",
                   "0101", "0110", "0111", "1000", "1001",
                   "0", "0", "0", "0", "0", "0", "0",
                   "1010", "1011", "1100", "1101", "1110", "1111"};

void input() {
    cin >> s;
    length = 0;
    ans = "";
    bs = "";
}

string ascii(int n) {
    string temp = "";
    do {
        temp += alphanum[n%16];
        n /= 16;
    } while (n);
    reverse(temp.begin(), temp.end());
    int len = temp.size();
    if (len == 1 || len == 3) temp = "0"+temp;
    return temp;
}

void convert_binary() {
    for (int i=0; i<(int)s.size(); i++) {
        bs += binary[s[i]-'0'];
    }
}

int number(int index) {
    string bits = bs.substr(index, 10);
    index += 10;
    int cnt = stoi(bits, 0, 2);
    string temp = "";
    int _dec = 0;
    while (cnt) {
        if (cnt >= 3) {
            temp = bs.substr(index, 10);
            _dec = stoi(temp, 0, 2);
            if (0 <= _dec && _dec <= 9) ans += ("00"+to_string(_dec));
            else if (10 <= _dec && _dec <= 99) ans += ("0"+to_string(_dec));
            else ans += to_string(_dec);
            cnt -= 3;
            index += 10;
            length += 3;
        } else if (cnt == 2) {
            temp = bs.substr(index, 7);
            _dec = stoi(temp, 0, 2);
            if (0 <= _dec && _dec <= 9) ans += ("0"+to_string(_dec));
            else ans += to_string(_dec);
            cnt -= 2;
            index += 7;
            length += 2;
        } else if (cnt == 1) {
            temp = bs.substr(index, 4);
            _dec = stoi(temp, 0, 2);
            ans += alphanum[_dec];
            cnt -= 1;
            index += 4;
            length += 1;
        }
    }
    return index;
}

int alpha(int index) {
    string bits = bs.substr(index, 9);
    index += 9;
    int cnt = stoi(bits, 0, 2);
    string temp = "";
    int _dec = 0;
    while (cnt) {
        if (cnt >= 2) {
            temp = bs.substr(index, 11);
            _dec = stoi(temp, 0, 2);
            ans += alphanum[_dec/45];
            ans += alphanum[_dec%45];
            cnt -= 2;
            index += 11;
            length += 2;
        } else if (cnt == 1) {
            temp = bs.substr(index, 6);
            _dec = stoi(temp, 0, 2);
            ans += alphanum[_dec%45];
            cnt -= 1;
            index += 6;
            length += 1;
        }
    }
    return index;
}

int eight(int index) {
    string bits = bs.substr(index, 8);
    index += 8;
    int cnt = stoi(bits, 0, 2);
    string temp = "";
    int _dec = 0;
    while (cnt--) {
        temp = bs.substr(index, 8);
        _dec = stoi(temp, 0, 2);
        if (_dec == 0x23) ans += "\\#";
        else if (_dec == 0x5c) ans += "\\\\";
        else if (0x20 <= _dec && _dec <= 0x7e) ans += (char)_dec;
        else ans += ("\\"+ascii(_dec));
        index += 8;
        length += 1;
    }
    return index;
}

int kanji(int index) {
    string bits = bs.substr(index, 8);
    index += 8;
    int cnt = stoi(bits, 0, 2);
    string temp = "";
    int _dec = 0;
    while (cnt--) {
        temp = bs.substr(index, 13);
        _dec = stoi(temp, 0, 2);
        ans += ("#"+ascii(_dec));
        index += 13;
        length += 1;
    }
    return index;
}

void solve(int index) {
    convert_binary();
    while (index < (int)bs.size()) {
        if (bs.compare(index, 4, "0001") == 0) index = number(index+4);
        else if (bs.compare(index, 4, "0010") == 0) index = alpha(index+4);
        else if (bs.compare(index, 4, "0100") == 0) index = eight(index+4);
        else if (bs.compare(index, 4, "1000") == 0) index = kanji(index+4);
        else if (bs.compare(index, 4, "0000") == 0) return;
        else return;
    }
}

int main() {
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        input();
        solve(0);
        cout << length << ' ' << ans << '\n';
    }
    return 0;
}




Python 3 소스코드


from sys import stdin
input = stdin.readline

for t in range(int(input())):
    ans = ''
    length = 0
    s = input().strip()

    def convert_binary(_hex):
        _bin = ''
        for i in range(len(_hex)):
            _bin += bin(int(_hex[i], 16))[2:].zfill(4)
        return _bin

    def number(index):
        global ans, length
        count_bit = int(bs[index:index+10], 2)
        index += 10
        while count_bit:
            if count_bit >= 3:
                ans += str(int(bs[index:index+10], 2)).zfill(3)
                count_bit -= 3
                index += 10
                length += 3
            elif count_bit == 2:
                ans += str(int(bs[index:index+7], 2)).zfill(2)
                count_bit -= 2
                index += 7
                length += 2
            elif count_bit == 1:
                ans += str(int(bs[index:index+4], 2))
                count_bit -= 1
                index += 4
                length += 1
        return index

    def alpha(index):
        alphanum = list('0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:')
        global ans, length
        count_bit = int(bs[index:index+9], 2)
        index += 9
        while count_bit:
            if count_bit >= 2:
                temp = int(bs[index:index+11], 2)
                ans += alphanum[temp//45]
                ans += alphanum[temp%45]
                count_bit -= 2
                index += 11
                length += 2
            elif count_bit == 1:
                temp = int(bs[index:index+6], 2)
                ans += alphanum[temp]
                count_bit -= 1
                index += 6
                length += 1
        return index

    def eight(index):
        global ans, length
        count_bit = int(bs[index:index+8], 2)
        index += 8
        for _ in range(count_bit):
            temp = int(bs[index:index+8], 2)
            if temp == 0x20:
                ans += ' '
            elif temp == 0x23:
                ans += '\\#'
            elif temp == 0x5c:
                ans += '\\\\'
            elif 0x20 <= temp <= 0x7e:
                ans += chr(temp)
            else:
                ans += ('\\'+hex(temp)[2:].upper().zfill(2))
            index += 8
            length += 1
        return index

    def kanji(index):
        global ans, length
        count_bit = int(bs[index:index+8], 2)
        index += 8
        for _ in range(count_bit):
            temp = int(bs[index:index+13], 2)
            ans += ('#'+hex(temp)[2:].upper().zfill(4))
            index += 13
            length += 1
        return index

    def solve(_index):
        while _index < len(bs):
            if bs[_index:_index+4] == "0001":
                _index = number(_index+4)
            elif bs[_index:_index+4] == "0010":
                _index = alpha(_index+4)
            elif bs[_index:_index+4] == "0100":
                _index = eight(_index+4)
            elif bs[_index:_index+4] == "1000":
                _index = kanji(_index+4)
            elif bs[_index:_index+4] == "0000":
                return
            else:
                return

    bs = convert_binary(s)
    solve(0)
    print(length, ans)




참고



태그