[LeetCode] 2483. Minimum Penalty for a Shop

https://leetcode.com/problems/minimum-penalty-for-a-shop/description/

Minimum Penalty for a Shop - LeetCode

문제 유형 : 구간 합(Prefix Sum)

문제 난이도 : Medium

 

문제

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.

 

문자 'N'과 'Y'로만 이루어진 문자열 customers가 있다.

Y는 가게에 손님이 온다는 뜻이고, N은 손님이 안온다는 뜻히다.

0시부터 N시(문자열의 길이)까지 중에서 문을 닫으려고 하는데, 최소 손해를 보는 시간중에 가장 빨리 닫는 시간을 구하시오.

 

가게가 열려있고 손님이 안오면 손해가 1 오르고, 가게가 닫혀있고 손님이 오면 손해가 1 오른다.

 

풀이

j시에 닫는다고 할 때의 손해 = 이전의 N의 개수 + 지금을 포함한 앞으로의 Y의 개수

 

이 때의 손해가 기존의 최소 손해보다 작으면 최소 손해값과 인덱스를 업데이트한다.

 

처음에 Y의 개수를 따로 구해놓고, 그 Y에다가 지금까지 찾은 y를 빼면 지금을 포함한 앞으로의 Y의 개수와 같다.

 

코드

C++

class Solution {
public:
    int bestClosingTime(string customers) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        const int n = customers.size();
        int Y = 0;

        for(int i = 0; i < n; i++) {
            Y += (customers[i] == 'Y'? 1:0);
        }

        int minPenalty = n;
        int time = n;
        int y_found = 0;
        int n_found = 0;

        for(int i = 0; i <=n; i++) {
            int y_remaining = Y - y_found;
            int penalty = y_remaining + n_found;

            if (penalty < minPenalty) {
                time = i;
                minPenalty = penalty;
            }

            if (i < n && customers[i] == 'N') {
                n_found++;
            }

            if(i < n && customers[i] == 'Y') {
                y_found++;
            }
        }

        return time;
    }
};

 

Python3

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        n = len(customers)
        Y = customers.count('Y')

        minPenalty = n
        time = n
        y_found = 0
        n_found = 0

        for i in range(n+1):
            y_remaining = Y - y_found

            penalty = n_found + y_remaining

            if penalty < minPenalty:
                minPenalty = penalty
                time = i

            if i < n and customers[i] == 'Y':
                y_found += 1
            if i < n and customers[i] == 'N':
                n_found += 1

        return time

 

Java

class Solution {
    public int bestClosingTime(String customers) {
        int n = customers.length();
        int Y = 0;
        for(int i = 0; i < n; i++) {
            Y += (customers.charAt(i) == 'Y'? 1:0);
        }

        int time = n;
        int minPenalty = n;
        int y_found = 0;
        int n_found = 0;

        for(int i = 0; i <= n; i++) {
            int y_remaining = Y - y_found;
            int penalty = n_found + y_remaining;

            if(penalty < minPenalty) {
                minPenalty = penalty;
                time = i;
            }

            if(i < n && customers.charAt(i) == 'N') {
                n_found++;
            }
            if(i < n && customers.charAt(i) == 'Y') {
                y_found++;
            }
        }

        return time;
    }
}