leetcode-solutions/2483.py at main · juneguo257/leetcode-solutions · GitHub

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
class Solution:
    def bestClosingTime(self, customers: str) -> int:
        # total penalty if shop closes at ith hour
        penaltyClosePrefix = [0 for _ in range(len(customers))]

        # total penalty if shop stays open till ith hour
        penaltyOpenPrefix = [0 for _ in range(len(customers))]

        for i in range(len(customers)-1, -1, -1):
            if (i == len(customers) - 1):
                if (customers[i] == "Y"):
                    penaltyClosePrefix[i] = 1
            else:
                if (customers[i] == "Y"):
                    penaltyClosePrefix[i] = 1 + penaltyClosePrefix[i+1]
                else:
                    penaltyClosePrefix[i] = penaltyClosePrefix[i+1]

        for i in range(len(customers)):
            if (i == 0):
                if (customers[i] == "N"):
                    penaltyOpenPrefix[i] = 1
            else:
                if (customers[i] == "N"):
                    penaltyOpenPrefix[i] = 1 + penaltyOpenPrefix[i-1]
                else:
                    penaltyOpenPrefix[i] = penaltyOpenPrefix[i-1]

        # add together and see
        minInd = 0
        for i in range(1, len(customers) + 1):
            if (minInd == 0):
                minSum = penaltyClosePrefix[0]
            else: # minInd > 0
                minSum = penaltyOpenPrefix[minInd - 1] + penaltyClosePrefix[minInd]

            if (i == len(customers)):
                curMinPenalty = penaltyOpenPrefix[-1]
            else: # i < len(customers)
                curMinPenalty = penaltyOpenPrefix[i-1] + penaltyClosePrefix[i]

            if (curMinPenalty < minSum):
                minInd = i

        return minInd