중고차

==================================================================== [ 주의 사항 ] ① 응시자는 User Code 안의 함수들을 구현해야 한다. ② User Code 안에는 어떠한 헤더 파일도 추가할 수 없다.     ( 단, malloc.h 사용 가능 ) ③ Input 파일은 사용되지 않는다. ④ Main 은 수정할 수 없으며, 실제 채점 시에도 그대로 사용된다.     ( 단, srand(3) 의 파라미터는 변경 ) ⑤ 본 검정은 C++ 언어만 지원한다. ==================================================================== 중고차 도매회사가 있다. 개인으로부터 중고차를 매입하고, 해외 판매사의 요청에 따라 수출한다. 이 회사의 재고 관리 프로그램을 작성하라.   void buy (CAR car)     개인으로부터 중고차를 매입한다.     void filter_by_age (int from, int to) void filter_by_passenger (int from, int to) void filter_by_engine (int from, int to) void filter_by_price (int from, int to)     판매사의 요구사항을 필터링한다. 필터링 조건은 아래와 같다. ( from ≤ X ≤ to ) 단, from 이 to 보다 클 경우 반대로 계산한다.     int sell (void)     필터링 결과에 해당하는 재고를 수출한다. age, passenger, engine, price 모든 조건을 만족해야 수출이 가능하다. 단, 환불을 위해 주문번호를 반환한다.     void refund (int order_number)     판매사의 요청에 의해 환불이 된다. 환불된 차량들은 재고 대수에 포함이 되며, 다시 수출이 가능하다.     int empty (void)     현재 남은 재고 대수를 반환하고, 창고를 비운다.   ※ PERFORMANCE 값이 작을수록 높은 점수를 받으며, 기타 자세한 사항은 주어진 코드를 분석하여 파악한다. ※ 제출 시 Result 값 : 오답의 개수 x 1,000,000 + PERFORMANCE [출력 예] 출력된 정답은 SCS(SW Certificate System) 와 Visual Studio 에서 서로 다르며, 각각의 출력 예는 아래와 같다.

#include <stdio.h> #include <stdlib.h> #include <time.h> struct CAR { int age; // 0 ~ 19 int passenger; // 2 ~ 12 int engine; // 1000 ~ 4999 int price; // 10000 ~ 39999 }; extern void buy(CAR car); extern void filter_by_age(int from, int to); extern void filter_by_passenger(int from, int to); extern void filter_by_engine(int from, int to); extern void filter_by_price(int from, int to); extern int sell(void); extern void refund(int order_number); extern int empty(void); static void build(CAR* car) { car->age = rand() % 20; car->passenger = 2 + (rand() % 11); car->engine = 1000 + (rand() % 4000); car->price = 10000 + (rand() % 30000); } static const int MAX_CAR = 1000000; int main(void) { setbuf(stdout, NULL); srand(3); int PERFORMANCE = 0; int order_number = -1; for (register int TRY = 1; TRY <= 10; TRY++) { printf("%d: ", TRY); time_t start = clock(); for (register int c = 0; c < MAX_CAR; c++) { CAR car; build(&car); buy(car); if ((rand() % 100) == 0) { filter_by_age(rand() % 20, rand() % 20); filter_by_passenger(2 + (rand() % 11), 2 + (rand() % 11)); filter_by_engine(1000 + (rand() % 4000), 1000 + (rand() % 4000)); filter_by_price(10000 + (rand() % 30000), 10000 + (rand() % 30000)); int ret = sell(); if ((rand() % 10) == 0) order_number = ret; } if ((rand() % 10000) == 0) { if (order_number != -1) { refund(order_number); order_number = -1; } } } int RESULT = empty(); order_number = -1; PERFORMANCE += ((clock() - start) / (CLOCKS_PER_SEC / 1000)); printf("STOCK = %d\n", RESULT); } printf("PERFORMANCE = %d\n", PERFORMANCE); return 0; }

struct CAR { int age; // 0 ~ 19 int passenger; // 2 ~ 12 int engine; // 1000 ~ 4999 int price; // 10000 ~ 39999 }; void buy(CAR car) { } void filter_by_age(int from, int to) { } void filter_by_passenger(int from, int to) { } void filter_by_engine(int from, int to) { } void filter_by_price(int from, int to) { } int sell(void) { return 0; // order_number ( >= 0) } void refund(int order_number) { } int empty(void) { return 0; }

struct CAR { int age; // 0 ~ 19 int passenger; // 2 ~ 12 int engine; // 1000 ~ 4999 int price; // 10000 ~ 39999 }; const int engsize = (5000 >> 8) + 2; const int prisize = (40000 >> 12) + 2; int tot = 0; CAR ori[1000005]; int head[20][13][engsize][prisize]; int next[1000005]; int sold[1000005], soldid[20000], soldtot, soldidtot; CAR left, right; bool isFirst = true; void init(); void buy(CAR car) { if (isFirst) init(); ori[tot] = car; int cur = head[car.age][car.passenger][car.engine >> 8][car.price >> 12]; next[tot] = cur; head[car.age][car.passenger][car.engine >> 8][car.price >> 12] = tot; tot++; } int sell(void) { for (int i = left.age; i <= right.age; i++) { for (int j = left.passenger; j <= right.passenger; j++) { for (int k = left.engine >> 8; k <= (right.engine >> 8); k++) { for (int l = left.price >> 12; l <= (right.price >> 12); l++) { int pos = head[i][j][k][l]; int prev = -1; while (pos != -1) { CAR *cur = &ori[pos]; if (cur->engine >= left.engine && cur->engine <= right.engine && cur->price >= left.price && cur->price <= right.price) { sold[soldtot++] = pos; if (prev == -1) head[i][j][k][l] = next[pos]; else next[prev] = next[pos]; } else prev = pos; pos = next[pos]; } } } } } soldid[soldidtot++] = soldtot; return soldidtot - 1; // order_number ( >= 0) } void refund(int order_number) { for (int i = soldid[order_number - 1]; i < soldid[order_number]; i++) { CAR *car = &ori[sold[i]]; int cur = head[car->age][car->passenger][car->engine >> 8][car->price >> 12]; next[sold[i]] = cur; head[car->age][car->passenger][car->engine >> 8][car->price >> 12] = sold[i]; } } int empty(void) { isFirst = true; int ret = 0; for (int i = 0; i < 20; i++) { for (int j = 0; j < 13; j++) { for (int k = 0; k < engsize; k++) { for (int l = 0; l < prisize; l++) { int pos = head[i][j][k][l]; while (pos != -1) { ret++; pos = next[pos]; } } } } } return ret; } void filter_by_age(int from, int to) { if (from > to) left.age = to, right.age = from; else left.age = from, right.age = to; } void filter_by_passenger(int from, int to) { if (from > to) left.passenger = to, right.passenger = from; else left.passenger = from, right.passenger = to; } void filter_by_engine(int from, int to) { if (from > to) left.engine = to, right.engine = from; else left.engine = from, right.engine = to; } void filter_by_price(int from, int to) { if (from > to) left.price = to, right.price = from; else left.price = from, right.price = to; } void init() { for (int i = 0; i < 20; i++) { for (int j = 0; j < 13; j++) { for (int k = 0; k < engsize; k++) { for (int l = 0; l < prisize; l++) { head[i][j][k][l] = -1; } } } } for (int i = 0; i < 20000; i++) { soldid[i] = 0; } soldtot = tot = 0; soldidtot = 1; isFirst = false; }