Problem A : Bit_ImageMap3
제한시간: 0 ms 메모리제한: 0 MB
채점준비중입니다.
사전에 영문 소문자 1~7자로 이루어진 1024개의 단어가 있다.
이 문자들을 무작위로 추출하여 작성된 문자열 배열을 받아서 이를 복원할 수 있도록 encode() 함수를 설계하고
원래의 문자열을 복원하는 decode() 함수를 작성하라.
가능한 공간을 최소로 사용해야 높은 점수를 얻을 수 있다.
자세한 내용은 아래의 코드를 참조하라.
//--------------main.cpp-----------------
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <time.h>
extern int encode(char* enc_str, char* str, int STRN);
extern void decode(char* dec_str, char* enc_str, int encn);
static unsigned int SEED = 12345;
const int STRN = 65535;
const int WORDN = 1024;
const int CHARN = 26;
int cnt[CHARN] = { 79,13,24,48,129,20,25,51,76,3,22,18,32,54,110,10,1,55,40,95,16,8,34,2,29,1 };
char charlist[996];
int wordlen[WORDN];
char words[WORDN][8];
char str[STRN];
char str_bak[STRN];
char enc_str[STRN];
char dec_str[STRN];
void build1()
{
int i, j, k = 0;
for (i = 0; i < CHARN; i++) for (j = 0; j < cnt[i]; j++) charlist[k++] = 'a' + i;
for (i = 0; i < WORDN; i++) {
wordlen[i] = rand() % 7 + 1;
for (j = 0; j < wordlen[i]; j++) words[i][j] = charlist[rand() % 995];
}
}
void build2()
{
int len = 0, i, k;
for (i = 0; i < STRN; i++)
str[i] = str_bak[i] = enc_str[i] = dec_str[i] = 0;
while (1) {
k = rand() % WORDN;
if (len + wordlen[k] >= STRN) break;
for (i = 0; i < wordlen[k]; i++) str[len++] = words[k][i];
str[len++] = ' ';
}
for (i = 0; i < STRN; i++) str_bak[i] = str[i];
}
int main()
{
srand(SEED);
int i, TC = 100;
long long score = 0;
build1();
time_t start = clock();
for (int t = 0; t < TC; t++) {
build2();
int encn = encode(enc_str, str, STRN);
for (i = encn; i < STRN; i++) enc_str[i] = 0;
decode(dec_str, enc_str, encn);
if (memcmp(dec_str, str_bak, STRN) != 0) score += 10000000;
else score += encn;
}
score += (long long)(clock() - start);
printf("SCORE: %lld\n", score / TC);
return 0;
}
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <time.h>
extern int encode(char* enc_str, char* str, int STRN);
extern void decode(char* dec_str, char* enc_str, int encn);
static unsigned int SEED = 12345;
const int STRN = 65535; // 전체 문장의 길이
const int WORDN = 1024;
const int CHARN = 26;
int cnt[CHARN] = { 79,13,24,48,129,20,25,51,76,3,22,18,32,54,110,10,1,55,40,95,16,8,34,2,29,1 };
char charlist[996];
int wordlen[WORDN];
char words[WORDN][8];
char str[STRN];
char str_bak[STRN];
char enc_str[STRN];
char dec_str[STRN];
void build1()
{
int i, j, k = 0;
for (i = 0; i < CHARN; i++) for (j = 0; j < cnt[i]; j++) charlist[k++] = 'a' + i; // 997개 빈도수에 따라 알파벳 저장함
for (i = 0; i < WORDN; i++) {
wordlen[i] = rand() % 7 + 1; // 단어의 길이
for (j = 0; j < wordlen[i]; j++) words[i][j] = charlist[rand() % 995]; // 단어 저장 사전
}
}
void build2()
{
int len = 0, i, k;
for (i = 0; i < STRN; i++)
str[i] = str_bak[i] = enc_str[i] = dec_str[i] = 0;
while (1) {
k = rand() % WORDN;
if (len + wordlen[k] >= STRN) break;
for (i = 0; i < wordlen[k]; i++) str[len++] = words[k][i];
str[len++] = ' ';
}
for (i = 0; i < STRN; i++) str_bak[i] = str[i]; // 복사 해둠
}
void output() {
freopen("output.txt", "w", stdout);
for (int i = 0; i < STRN; i++) {
printf("%c", str_bak[i]);
}
}
int main()
{
srand(SEED);
int i, TC = 1;
long long score = 0;
build1();
time_t start = clock();
for (int t = 0; t < TC; t++) {
build2();
// output();
int encn = encode(enc_str, str, STRN);
for (i = encn; i < STRN; i++) enc_str[i] = 0;
decode(dec_str, enc_str, encn);
if (memcmp(dec_str, str_bak, STRN) != 0) score += 10000000;
else score += encn;
}
score += (long long)(clock() - start);
printf("SCORE: %lld\n", score / TC);
return 0;
}
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
//dic + huf
#include <string.h>
void set(char* str, int p, int bit)
{
if (bit == 0) return;
str[p / 8] |= (128 >> (p % 8));
}
int get(char* str, int p)
{
return (str[p / 8] >> (7 - p % 8)) & 1;
}
void setnum(char* str, int num, int &p, int n)
{
for (int i = p, j = n - 1; i < p + n; i++, j--)
set(str, i, (num >> j) & 1); // 비트 연산
p += n;
}
int getnum(char* str, int &p, int n)
{
int k = 0;
for (int i = p; i < p + n; i++)
k = (k << 1) + get(str, i);
p += n;
return k;
}
struct data {
int val, cnt;
data* left, *right;
data *myAlloc(int _val, int _cnt, data* l, data* r) {
val = _val, cnt = _cnt, left = l, right = r;
return this;
}
};
void in_sort(data *chr[], int p)
{
for (int i = p; i > 0; i--) {
if (chr[i - 1]->cnt >= chr[i]->cnt) break; // 허프만 트리 만드는 과정, cnt 확인
data* tmp = chr[i - 1];
chr[i - 1] = chr[i];
chr[i] = tmp;
}
}
void make(data *node, int num, int alpha[])
{
if (node->val >= 0) {
alpha[node->val] = num;
return;
}
make(node->left, (num << 1), alpha);
make(node->right, (num << 1) + 1, alpha);
}
void setch(char* str, int num, int &p)
{
if (num <= 1) return;
setch(str, num >> 1, p);
set(str, p++, num & 1);
}
int getch(char* str, int &p, data* node)
{
if (node->val >= 0) return node->val;
if (get(str, p) == 0) return getch(str, ++p, node->left);
else return getch(str, ++p, node->right);
}
void huf(data *chr[], data arr[], int alpha[])
{
int i, k = 0;
int chcnt[26] = { 79,13,24,48,129,20,25,51,76,3,22,18,32,54,110,10,1,55,40,95,16,8,34,2,29,1 };
for (i = 0; i < 26; i++) {
chr[i] = arr[k++].myAlloc(i, chcnt[i], 0, 0);
in_sort(chr, i);
}
for (i = 24; i >= 0; i--) {
chr[i] = arr[k++].myAlloc(-1, chr[i]->cnt + chr[i + 1]->cnt, chr[i], chr[i + 1]);
in_sort(chr, i);
}
make(chr[0], 1, alpha);
//for (i = 0; i < 26; i++) printf("%d ", alpha[i]);
}
int search(char dic[1000][8], int &n, char word[])
{
for (int i = 0; i < n; i++) {
if (strcmp(dic[i], word) == 0) return i; // 같으면
}
strcpy(dic[n], word);
return n++;
}
int encode(char* enc_str, char* str, int STRN)
{
data* root, *chr[30], arr[60];
int alpha[26];
huf(chr, arr, alpha); // 빈도수에 따라서 bit로 만들음
int i, j, dicn = 0, wordn = 0, cnt = 0, p = 0, len;
char dic[1000][8], word[8];
int wnum[14000];
for (i = 0; i < STRN; i++) {
if (str[i] == ' ') {
word[cnt] = 0; // 단어 끝맺음
wnum[wordn++] = search(dic, dicn, word); // 같은 단어 있음 정리함. dicn 총 단어 수
cnt = 0;
}
else {
word[cnt++] = str[i];
}
}
setnum(enc_str, dicn, p, 10); // enc_str 어떤 작업?
for (i = 0; i < dicn; i++) {
len = strlen(dic[i]);
setnum(enc_str, len, p, 3);
for (j = 0; j < len; j++) {
setch(enc_str, alpha[dic[i][j] - 'a'], p);
}
}
setnum(enc_str, wordn, p, 14);
for (i = 0; i < wordn; i++) {
setnum(enc_str, wnum[i], p, 10);
}
return (p + 7) / 8;
}
void decode(char* dec_str, char* enc_str, int encn)
{
data* root, *chr[30], arr[60];
int alpha[26];
huf(chr, arr, alpha);
int i, j, dicn, wordn, cnt, p = 0, dicnum;
char dic[1000][9] = { {0} }, word[8];
dicn = getnum(enc_str, p, 10);
for (i = 0; i < dicn; i++) {
cnt = getnum(enc_str, p, 3);
for (j = 0; j < cnt; j++) {
dic[i][j] = getch(enc_str, p, chr[0]) + 'a';
}
dic[i][j] = ' ';
}
wordn = getnum(enc_str, p, 14);
for (i = 0; i < wordn; i++) {
dicnum = getnum(enc_str, p, 10);
strcat(dec_str, dic[dicnum]);
}
}ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
//허프만
#include <stdio.h>
void set(char* str, int p, int bit)
{
if (bit == 0) return;
str[p / 8] = (128 >> (p % 8));
}
int get(char* str, int p)
{
return (str[p / 8] >> (7 - p % 8)) & 1;
}
void setnum(char* str, int num, int p, int n)
{
for (int i = p, j = n - 1; i < p + n; i++, j--)
set(str, i, (num >> j) & 1);
}
int getnum(char* str, int p, int n)
{
int k = 0;
for (int i = p; i < p + n; i++)
k = (k << 1) + get(str, i);
return k;
}
struct data {
int val, cnt;
data* left, *right;
data *myAlloc(int _val, int _cnt, data* l, data* r) {
val = _val, cnt = _cnt, left = l, right = r;
return this;
}
} *root, *chr[30];
int* alpha;
void in_sort(int p)
{
for (int i = p; i > 0; i--) {
if (chr[i - 1]->cnt >= chr[i]->cnt) break;
data* tmp = chr[i - 1];
chr[i - 1] = chr[i];
chr[i] = tmp;
}
}
void make(data *node, int num)
{
if (node->val >= 0) {
alpha[node->val] = num;
return;
}
make(node->left, (num << 1));
make(node->right, (num << 1) + 1);
}
void setch(char* str, int num, int &p)
{
if (num <= 1) return;
setch(str, num >> 1, p);
set(str, p++, num & 1);
}
int getch(char* str, int &p, data* node)
{
if (node->val >= 0) return node->val;
if (get(str, p) == 0) return getch(str, ++p, node->left);
else return getch(str, ++p, node->right);
}
void huf(data arr[])
{
int i, k = 0;
int chcnt[26] = { 79,13,24,48,129,20,25,51,76,3,22,18,32,54,110,10,1,55,40,95,16,8,34,2,29,1 };
for (i = 0; i < 26; i++) {
chr[i] = arr[k++].myAlloc(i, chcnt[i], 0, 0);
in_sort(i);
}
for (i = 24; i >= 0; i--) {
chr[i] = arr[k++].myAlloc(-1, chr[i]->cnt + chr[i + 1]->cnt, chr[i], chr[i + 1]);
in_sort(i);
}
root = chr[0];
make(root, 1);
//for (i = 0; i < 26; i++) printf("%d ", alpha[i]);
}
int encode(char* enc_str, char* str, int STRN)
{
data arr[60];
int alnum[26];
alpha = alnum;
huf(arr);
int i, cnt = 0, cntp = 0, p = 3;
for (i = 0; i < STRN; i++) {
if (str[i] == ' ') {
setnum(enc_str, cnt, cntp, 3);
cnt = 0;
cntp = p;
p += 3;
}
else {
setch(enc_str, alpha[str[i] - 'a'], p);
cnt++;
}
}
return (p + 7) / 8;
}
void decode(char* dec_str, char* enc_str, int encn)
{
data arr[60];
int alnum[26];
alpha = alnum;
huf(arr);
int cnt, p = 0, dp = 0;
while (1) {
cnt = getnum(enc_str, p, 3);
p += 3;
if (cnt == 0) break;
while (cnt--) {
dec_str[dp++] = getch(enc_str, p, root) + 'a';
}
dec_str[dp++] = ' ';
}
}
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
//bitmap3 최종
#include <string.h>
void set(char* str, int p, int bit)
{
if (bit == 0) return;
str[p / 8] |= (128 >> (p % 8));
}
int get(char* str, int p)
{
return (str[p / 8] >> (7 - p % 8)) & 1;
}
void setnum(char* str, int num, int &p, int n)
{
for (int i = p, j = n - 1; i < p + n; i++, j--)
set(str, i, (num >> j) & 1);
p += n;
}
int getnum(char* str, int &p, int n)
{
int k = 0;
for (int i = p; i < p + n; i++)
k = (k << 1) + get(str, i);
p += n;
return k;
}
int search(char dic[1000][8], int &n, char word[])
{
for (int i = 0; i < n; i++) {
if (strcmp(dic[i], word) == 0) return i;
}
strcpy(dic[n], word);
return n++;
}
int encode(char* enc_str, char* str, int STRN)
{
int i, j, dicn = 0, wordn = 0, cnt = 0, p = 0, len;
char dic[1000][8], word[8];
int wnum[14000];
for (i = 0; i < STRN; i++) {
if (str[i] == ' ') {
word[cnt] = 0;
wnum[wordn++] = search(dic, dicn, word);
cnt = 0;
}
else {
word[cnt++] = str[i];
}
}
setnum(enc_str, dicn, p, 10);
for (i = 0; i < dicn; i++) {
len = strlen(dic[i]);
setnum(enc_str, len, p, 3);
for (j = 0; j < len; j++) {
setnum(enc_str, dic[i][j] - 'a', p, 5);
}
}
setnum(enc_str, wordn, p, 14);
for (i = 0; i < wordn; i++) {
setnum(enc_str, wnum[i], p, 10);
}
return (p + 7) / 8;
}
void decode(char* dec_str, char* enc_str, int encn)
{
int i, j, dicn, wordn, cnt, p = 0, dicnum;
char dic[1000][9] = { {0} }, word[8];
dicn = getnum(enc_str, p, 10);
for (i = 0; i < dicn; i++) {
cnt = getnum(enc_str, p, 3);
for (j = 0; j < cnt; j++) {
dic[i][j] = getnum(enc_str, p, 5) + 'a';
}
dic[i][j] = ' ';
}
wordn = getnum(enc_str, p, 14);
for (i = 0; i < wordn; i++) {
dicnum = getnum(enc_str, p, 10);
strcat(dec_str, dic[dicnum]);
}
}'Computer Science' 카테고리의 다른 글
| 5 Problem B : 최단경로 (0) | 2020.02.04 |
|---|---|
| 5 Problem A : 지하철 (0) | 2020.02.04 |
| Problem D : 어디 있니?( where are you?) (0) | 2020.01.28 |
| 4 Problem C : 숫자 야구2 (0) | 2020.01.27 |
| 4 Problem B : 타일 채우기 (0) | 2020.01.13 |
댓글