중고차 솔루션

1. 링크드 리스트 2. 나누어서 저장하기 3. 탐색에 용이함 4. 적절한 숫자를 찾기 5. 비트연산자 활용하기

#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 }; 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; }