Daily LeetCoding Challenge 2483. Minimum Penalty for a Shop

Leetcode 75 스터디 플랜이 끝났다. 앞으로는 Daily LeetCoding Challenge를 풀어볼 생각이다.

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

Minimum Penalty for a Shop - LeetCode

문제 설명

문자열 customers는 'Y' 또는 'N'으로만 이뤄졌는데, 각 문자는 i번째 시간에 손님이 방문 또는 방문하지 않음을 나타낸다. 가게를 닫는 시간을 j (0 <= j <= customers.length())라고 했을 때, 가게를 열어뒀는데 손님이 없다면 페널티 1이 있고, 가게를 닫았는데 손님이 온다면 페널티 1이 있다. 이때 페널티를 최소화하면서 가게를 가장 일찍 닫을 수 있는 시간을 반환하라.

직관

상점을 열고 손님이 없을 때의 페널티(openPenalty)와 상점을 닫고 손님이 방문했을 때의 페널티(closePenalty)는 시간 j에 따라 달라진다.

접근법

첫 번째 루프에서 customers 문자열을  순회하여 0번째 시간에 상점을 닫았을 때에 대한 페널티를 계산한다. 0번째 시간에는 오픈 페널티가 없다.
다음 루프에서는 폐점 시간 i를 1부터 customers.length()까지 이동한다. 매 시간마다 고객 방문이 없는 경우 오픈 페널티는 누적되고, 고객 방문이 있는 경우 클로즈 페널티는 감소한다.

복잡도

시간 복잡도는 O(n), 공간 복잡도는 O(1)이다.

코드

class Solution {
    public int bestClosingTime(String customers) {
        int hour=0, n=customers.length();
        // compute penalty for closing the shop at 0
        int closePenalty=0;
        for(int i=0; i<n; i++) {
            if (customers.charAt(i) == 'Y') {
                closePenalty++;
            }
        }
        int openPenalty=0;
        int penalty = openPenalty + closePenalty;
        for(int i=1; i<=n; i++) {
            if (customers.charAt(i-1) == 'N') {
                openPenalty++;
            }
            if (customers.charAt(i-1) == 'Y') {
                closePenalty--;
            }
            if (openPenalty + closePenalty < penalty) {
                penalty = openPenalty + closePenalty;
                hour = i;
            }
        }
        return hour;
    }
}