30049 c++ - 영업의 신

요즘은 백준에서 랜덤 마라톤 문제를 풀고 있습니다. 그중 오늘은 G번 문제인 30049번 문제를 풀도록 하겠습니다.

 

구현 문제입니다.

 

https://www.acmicpc.net/problem/30049

 

시간복잡도를 상수시간에 맞춰서 코드를 작성해야합니다.

 

#include <iostream>

#define FASTIO ios::sync_with_stdio(0), cin.tie(0)

using namespace std;

int marketBestSeller[10000];
int bestSellerCount[300];
int salesTable[10000][300];
int maxSales[10000];

int countBestSeller(int employeeCount, int chargeCount) {
  int count = 0;
  for (int i = 0; i < employeeCount; i++) {
    if (bestSellerCount[i] == chargeCount) {
      count++;
    }
  }
  return count;
}

int main() {
  FASTIO;

  int n, m, k;
  cin >> n >> m >> k;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < k; j++) {
      int store, sales;
      cin >> store >> sales;
      salesTable[store - 1][i] = sales;
      maxSales[store - 1] = max(maxSales[store - 1], sales);
    }
  }

  for (int i = 0; i < m; i++) {
    if (maxSales[i] == 0) continue;
    for (int j = 0; j < n; j++) {
      if (salesTable[i][j] == maxSales[i]) {
        ++bestSellerCount[j];
        marketBestSeller[i] = j;
        break;
      }
    }
  }

  int tasks;
  cin >> tasks;

  for (int i = 0; i < tasks; i++) {
    int employee, store, sales;
    cin >> employee >> store >> sales;
    store--;
    employee--;

    if (marketBestSeller[store] == employee) {
      salesTable[store][employee] += sales;
      maxSales[store] = salesTable[store][employee];
    } else {
      salesTable[store][employee] += sales;
      if (salesTable[store][employee] > maxSales[store]) {
        maxSales[store] = salesTable[store][employee];
        bestSellerCount[marketBestSeller[store]]--;
        marketBestSeller[store] = employee;
        bestSellerCount[employee]++;
      }
    }

    cout << countBestSeller(n, k) << "\n";
  }

  return 0;
}