반응형
알고리즘 분류 : 시뮬레이션, 문자열 처리
이 문제는 최소 사이즈(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)
참고
반응형