창고관리(Warehouse manager) timer 4s memory 128MB

창고형 대형매장에서 창고관리를 하고 있는 정올이는 창고에 상품들이 여기저기 흩어져 있어서 

새로운 상품이 입고되거나 주문을 받아서 상품을 출고할 때마다 많은 어려움을 겪고 있다.

이번 기회에 창고를 정리하여 이러한 문제들을 해결하고자 한다.

창고에는 상품을 넣을 수 있는 공간이 일렬로 배치되어 있으며 새로운 상품이 입고될 때마다 

연속된 빈 공간에 상품을 적재했다가 출고 요청이 있으면 순차적으로 출고하는 시스템이다.

현재 창고의 상태를 입력으로 받아서 아래의 규칙에 맞도록 정리하는 cleanup() 함수를 작성하시오.

입력으로 주어지는 창고의 정보는 아래와 같다.

1. 각각의 상품은 상품번호로 구분된다.  상품번호는 1이상 9이하의 정수이다.

2. 창고에는 상품 저장을 위해 일렬로 이루어진 N개의 block이 있다. (200 ≤ houseSize ≤20,000)

3. 창고의 개별 block마다 보관된 상품의 번호가 표시되어 있으며 비어있는 block은 0으로 표시된다.

4. 입력으로 주어지는 창고의 초기 상태에서는 같은 번호를 가지는 상품 block들이 최소 8개 이상 연속되어 있다. 

(빈 공간을 나타내는 0인 block도 최소 8개 이상 연속되어 있고 0인 block은 반드시 존재한다.)​ 

창고의 정리는 다음과 같은 원칙으로 진행한다.

1. 같은 종류의 상품들은 모두 연속된 block에 저장되어야 한다.

즉, 같은 번호를 가진 block들 사이에 다른 번호의 block이나 빈 공간(번호가 0인 block)이 있어서는 안 된다.

2. 빈 공간인 block(번호가 0인 block)은 창고의 마지막 부분에 위치해야 한다. 즉, 모든 상품의 block은 빈 공간의 block보다 앞서 있어야 한다.

3. 상품을 정리한 후 각 종류별 상품의 개수는 창고정리 전과 동일하여야 한다.

4. 자세한 동작원리는 제공되는 코드를 분석하여 확인해야 한다.

5. 전체 이동횟수가 N의 1/10 이상이 되어서는 안된다.​ 

예를 들어 창고의 상태가 아래와 같이 입력되었다고 하자. (이해를 돕기 위한 것으로 전체 길이 및 연속된 데이터의 개수는 입력조건과 다를 수 있다.)

33333333000000111111222233334444444444400000000000002222222222200000

아래의 자료들은 창고정리가 잘 된 상태를 나타낸다.

11111133333333333344444444444222222222222222000000000000000000000000 33333333333311111144444444444222222222222222000000000000000000000000 44444444444333333333333111111222222222222222000000000000000000000000 11111122222222222222233333333333344444444444000000000000000000000000

하지만 다음과 같은 자료는 빈 공간(0인 블럭)이 중간에 있어서 잘못된 경우이다.

11111122222222222222233333333333300000000000000000000000044444444444

다음의 경우는 2번 상품이 두 곳으로 나누어져 있어서 잘못된 경우이다.

33333333111111222233334444444444422222222222000000000000000000000000

입력자료는 main에서 자동으로 생성되므로 cleanup() 함수만 작성해서 제출하면 된다.

기타 필요한 배열이나 변수, 함수 등은 추가로 작성해서 제출할 수 있으나 main 함수를 포함한 주어지는 프로그램은 채점시에 함께 컴파일되어 실행된다.

메인의 srand(5)  부분의 괄호안 숫자는 임의로 변경되어 채점될 것이다. 

기타 자세한 내용은 아래의 소스부분을 분석하여 작성하라.

/// *** user.cpp ***
void cleanup(){
 
}
 
/// *** main.cpp ***
#include <stdio.h>
#include <stdlib.h>
#define HOUSE_SIZE  20000
#define BLANK_SIZE   64
#define MAX_HOUSE   10
#define MAX_COUNT (HOUSE_SIZE * 2 * 50) 
 
using namespace std;
 
static int house[HOUSE_SIZE];
static int blank[BLANK_SIZE];
static int numCount[MAX_HOUSE];
static int moveCount;
static int houseSize;
static int totalMoveCount;
static int totalhouseSize;
 
extern void cleanup();
 
int gethouseSize()
{
    return houseSize;
}
 
int readhouse(int* blank, int address, int size)
{
    if (address < 0 || address + size > houseSize)
        return 0;
 
    for (int i = 0; i < size; i++)
        blank[i] = house[address++];
 
    return size;
}
 
int move(int from, int to, int size)
{
    if (moveCount < MAX_COUNT)
        moveCount++;
 
    if (from < 0 || from >= houseSize || to < 0 || to >= houseSize)
        return 0;
 
    if (size < 1 || size > BLANK_SIZE || from + size > houseSize || to + size > houseSize)
        return 0;
 
    for (int i = 0; i < size; i++)
    {
        blank[i] = house[from];
        house[from] = 0;
        from++;
    }
 
    for (int i = 0; i < size; i++)
    {
        house[to++] = blank[i];
    }
    return size;
}
 
static int checkhouse()
{
    int checkCount[MAX_HOUSE];
    for (int i = 0; i < MAX_HOUSE; i++)
        checkCount[i] = 0;
 
    int idx = 0;
    while (idx < houseSize)
    {
        int houseID = house[idx];
        if (checkCount[houseID] != 0)
            return 0;
 
        for (int i = 0; i < numCount[houseID]; i++)
        {
            if (houseID != house[idx++])
                return 0;
            checkCount[houseID]++;
        }
    }
 
    if (house[houseSize - 1] != 0)
        return 0;
 
    for (int i = 0; i < MAX_HOUSE; i++)
    {
        if (checkCount[i] != numCount[i])
            return 0;
    }
 
    return 1;
}
 
static void init()
{
    moveCount = 0;
 
    for (int i = 0; i < MAX_HOUSE; i++)
        numCount[i] = 0;
 
    for (int i = 0; i < houseSize; i++)
    {
        numCount[house[i]]++;
    }
}
 
 
int main()
{
    setbuf(stdout, NULL);
    srand(5);
    const int T = 100;
 
    totalMoveCount = 0;
    totalhouseSize = 0;
    int num, ea;
    for (int tc = 1; tc <= T; tc++)
    {
        houseSize = rand() % (HOUSE_SIZE - 200) + 200;
        int k = 0, flag = 0;
        while (k < houseSize - BLANK_SIZE) {
            ea = rand() % 57 + 8;
            if (k > houseSize / 2 && flag == 0) num = 0;
            else num = rand() % 10;
            if (num == 0) flag = 1;
            while (ea--) house[k++] = num;
        }
        while (k < houseSize) house[k++] = 0;
        init();
        cleanup();
 
        int cnt = MAX_COUNT;
        if (checkhouse() == 1)
            cnt = moveCount;
 
        printf("#%d %d\n", tc, cnt);
 
        totalMoveCount += cnt;
        totalhouseSize += houseSize;
    }
 
    printf("Total houseSize  : %d\n", totalhouseSize);
    printf("Total moveCount : %d\n", totalMoveCount);
}