[H2104] 창고 관리

out.swexpertacademy.samsung.com/common/swea/solvingPractice/problemResult.do?contestProbId=AXdf-YkAShBqnWAH&ocwKind=&ocwSeq=&solveclubId=&solveclubPassword=&attendYn=

Information Message

- 구조체 사용

- 구조체, 포인터 사용 복습 필요

- 해쉬 사용을 유연하게.

#define RINT register int 
#define ULL unsigned long long 
void mstrcpy(char* dest, const char* src)
{
    int i = 0;
    while (src[i] != '\0')
    {
        dest[i] = src[i];
        i++;
    }
    dest[i] = src[i];
}

// 추가된 도형들을 모두 저장해서 겹치는지 확인할 때 사용
struct rect
{
    char name[11];
    ULL lname;
    char tag[11];
    int sr, sc;
    int h, w;
    int er, ec;
    int del;
    //rect *next, *prev;
}S[310]; //square
int s_cnt;

struct tag
{
    char name[11];
    ULL lname;
    int del;
    int cnt;
    int n_lists[300];
    //rect head, tail;
}T[310];
int t_cnt;
int map[302][302];
int R, C;

ULL char2ull(char* str) {
    ULL value = 0;
    while (*str) {
        value = (value << 5) + (*str++ - 'a' + 11);
    }
    return value;
}
#define MAX_TABLE 607
struct HASH {
    typedef struct
    {
        ULL key;
        int idx;
        int del;
    }Hash;
    Hash tb[MAX_TABLE];

    void init()
    {
        for (int i = 0; i < MAX_TABLE; i++)tb[i] = Hash();
    }
    int find(ULL key, int* idx)
    {
        ULL h = key % MAX_TABLE;
        int cnt = MAX_TABLE;

        while (tb[h].key != 0 && cnt--)
        {
            if (tb[h].key == key)
            {
                *idx = tb[h].idx;
                return 1;
            }
            h = (h + 1) % MAX_TABLE;
        }
        return 0;
    }


    int add(ULL key, int idx)
    {
        //unsigned long h = hash(key);
        ULL h = key % MAX_TABLE;

        while (tb[h].key != 0 && !tb[h].del)
        {
            if (tb[h].key == key && !tb[h].del)
            {
                return 0;
            }

            h = (h + 1) % MAX_TABLE;
        }
        tb[h].key = key;
        tb[h].idx = idx;
        tb[h].del = 0;
        return 1;
    }

    int del(ULL key)
    {
        //unsigned long h = hash(key);
        ULL h = key % MAX_TABLE;
        int cnt = MAX_TABLE;

        while (tb[h].key != 0 && cnt--)
        {
            if (tb[h].key == key && !tb[h].del)
            {
                tb[h].del = 1;
                return 1;
            }
            h = (h + 1) % MAX_TABLE;
        }
        return 0;
    }
} HN, HT;

// 다른 도형들과 겹치는지 확인
int is_cross(int sr, int sc, int er, int ec)
{
    if (map[er][ec]) return map[er][ec]; 
    for (RINT i = 1; i < s_cnt; i++)
    {
        if (S[i].del == 0) { // 삭제 여부
            if (!(S[i].ec < sc || ec < S[i].sc || er < S[i].sr || sr > S[i].er)) return i;
        }
    }
    return 0;
}

struct Best_Pos
{
    int r, c;
};

// 이곳은 재귀로 구현함
Best_Pos find_best_pos(int sr, int sc, int height, int width, int next = C)
{

    int er = sr + height - 1;
    int ec = sc + width - 1;

    if (ec > C) return { 0,0 };
    if (er > R) return find_best_pos(1, next + 1, height, width, C);
    int bid;
    if ((bid = is_cross(sr, sc, er, ec)) == 0)
    {
        return { sr,sc };
    }
    else
    {
        if (next > S[bid].ec) next = S[bid].ec;
        return find_best_pos(S[bid].er + 1, sc, height, width, next);
    }
}

void set_map(int sr, int sc, int er, int ec, int value)
{
    for (RINT r = sr; r <= er; r++)
        for (RINT c = sc; c <= ec; c++) map[r][c] = value;
}

void init(int R, int C)
{
    ::R = R;
    ::C = C;
    for (RINT r = 1; r <= R; r++)
        for (RINT c = 1; c <= C; c++)map[r][c] = 0;
    s_cnt = t_cnt = 1;
    HN.init();
    HT.init();
}

int addItem(char name[], char tag[], int height, int width, int mode, int r, int c) {

    if (mode == 0)// 수동
    {
        if (map[r][c] != 0) return 0; // 해당 칸이 비어있는지 확인
        if (r + height - 1 > R || c + width - 1 > C) return 0; // 도형이 맵을 벗어나는지 확인 
        if (is_cross(r, c, r + height - 1, c + width - 1)) return 0;
    }
    else//자동
    {
        Best_Pos ret;
        ret = find_best_pos(1, 1, height, width, C);
        if (ret.r == 0) return 0;
        r = ret.r;
        c = ret.c;
    }

    rect& rt = S[s_cnt];

    mstrcpy(rt.name, name);
    mstrcpy(rt.tag, tag);
    rt.lname = char2ull(name);
    rt.sr = r;
    rt.sc = c;
    rt.h = height;
    rt.w = width;
    rt.er = r + height - 1;
    rt.ec = c + width - 1;
    rt.del = 0;

    HN.add(rt.lname, s_cnt);

    int tidx = 0;
    ULL tkey = char2ull(tag);
    if (HT.find(tkey, &tidx) == 0)// 신규 tag 등록
    {
        tidx = t_cnt;
        mstrcpy(T[t_cnt].name, tag);
        T[t_cnt].cnt = 0;
        T[t_cnt].lname = tkey;
        HT.add(tkey, t_cnt);
        t_cnt++;
    }

    T[tidx].n_lists[T[tidx].cnt++] = s_cnt;
    set_map(rt.sr, rt.sc, rt.er, rt.ec, s_cnt);
    s_cnt++;
    return 1;
}

int removeItemByName(char name[]) {

    ULL key = char2ull(name);
    int idx = 0;
    if (HN.find(key, &idx) == 0) return 0;
    HN.del(key);
    rect& rt = S[idx];
    if (rt.del == 1) return 0;
    rt.del = 1;
    set_map(rt.sr, rt.sc, rt.er, rt.ec, 0);
    return 1;
}

int removeItemByTag(char tag[]) {

    ULL tkey = char2ull(tag);
    int tidx = 0;
    int cnt = 0;
    if (HT.find(tkey, &tidx) == 0) return 0;

    for (RINT i = 0; i < T[tidx].cnt; i++)
    {
        int id = T[tidx].n_lists[i];
        if (S[id].del == 0) {
            S[id].del = 1;
            set_map(S[id].sr, S[id].sc, S[id].er, S[id].ec, 0);
            cnt++;
        }
    }
    T[tidx].cnt = 0;
    return  cnt;
}

int getItem(int r, int c, char name[], char tag[]) {

    if (map[r][c] == 0) return 0;

    rect& rt = S[map[r][c]];

    mstrcpy(name, rt.name);
    mstrcpy(tag, rt.tag);


    return 1;
}

int getArea(char tag[]) {

    int area = 0;
    ULL tkey = char2ull(tag);
    int tidx = 0;

    if (HT.find(tkey, &tidx) == 0) return 0;

    for (RINT i = 0; i < T[tidx].cnt; i++)
    {
        int id = T[tidx].n_lists[i];
        if (S[id].del == 0)area += (S[id].h * S[id].w);
    }
    return area;
}