aboutsummaryrefslogtreecommitdiff
path: root/min_penalty_shop.c
blob: 4e410536b5b7ff757f07694e8ba2b8785730d9c2 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 2483. Minimum Penalty for a Shop
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 You are given the customer visit log of a shop represented by a 0-indexed
string customers consisting only of characters 'N' and 'Y':

    if the ith character is 'Y', it means that customers come at the ith hour
    whereas 'N' indicates that no customers come at the ith hour.

If the shop closes at the jth hour (0 <= j <= n), the penalty is calculated as
follows:

    For every hour when the shop is open and no customers come, the penalty
increases by 1. For every hour when the shop is closed and customers come, the
penalty increases by 1.

Return the earliest hour at which the shop must be closed to incur a minimum
penalty.

Note that if a shop closes at the jth hour, it means the shop is closed at the
hour j.
*/

int bestClosingTime(char *customers) {
  int n = strlen(customers);
  int *pre_n = malloc((n + 1) * sizeof(int));
  int *suf_y = malloc((n + 1) * sizeof(int));
  pre_n[0] = 0;
  for (int i = 0; i < n; i++) {
    pre_n[i + 1] = pre_n[i];
    if (customers[i] == 'N')
      pre_n[i + 1]++;
  }
  suf_y[n] = 0;
  for (int i = n - 1; i >= 0; i--) {
    suf_y[i] = suf_y[i + 1];
    if (customers[i] == 'Y')
      suf_y[i]++;
  }
  int min = INT_MAX, min_id = 0;
  for (int i = 0; i <= n; i++) {
    int d = pre_n[i] + suf_y[i];
    if (d < min) {
      min = d;
      min_id = i;
    }
    if (!min)
      break;
  }
  free(pre_n), free(suf_y);
  return min_id;
}

int main() {
  char c1[] = {"YYNY"}, c2[] = {"NNNNN"}, c3[] = {"YYYY"};
  printf("%d\n", bestClosingTime(c1)); // expect: 2
  printf("%d\n", bestClosingTime(c2)); // expect: 0
  printf("%d\n", bestClosingTime(c3)); // expect: 4
}