[LeetCode] 2483. Minimum Penalty for a Shop - Java

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

Minimum Penalty for a Shop - LeetCode

---

문제

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.

 

Example 1:

Input: customers = "YYNY"
Output: 2
Explanation: 
- Closing the shop at the 0th hour incurs in 1+1+0+1 = 3 penalty.
- Closing the shop at the 1st hour incurs in 0+1+0+1 = 2 penalty.
- Closing the shop at the 2nd hour incurs in 0+0+0+1 = 1 penalty.
- Closing the shop at the 3rd hour incurs in 0+0+1+1 = 2 penalty.
- Closing the shop at the 4th hour incurs in 0+0+1+0 = 1 penalty.
Closing the shop at 2nd or 4th hour gives a minimum penalty. Since 2 is earlier, the optimal closing time is 2.

Example 2:

Input: customers = "NNNNN"
Output: 0
Explanation: It is best to close the shop at the 0th hour as no customers arrive.

Example 3:

Input: customers = "YYYY"
Output: 4
Explanation: It is best to close the shop at the 4th hour as customers arrive at each hour.

Constraints:

• 1 <= customers.length <= 105
• customers consists only of characters 'Y' and 'N'.

---

풀이

풀이 과정

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

문자열 customers의 각 자리는 i번째 시간에 매장에 방문한 사람이 있는지 여부를 나타낸다. 즉 "YYNY"의 경우 0, 1, 3번째 시간에는 매장에 손님이 방문했고, 2번째 시간에는 손님이 방문하지 않았음을 뜻한다.

만약 특정 시간에 가게가 문을 닫는 경우 패널티가 발생 하는데 패널티는 다음과 같이 계산된다.
가게의 문이 열려있는 동안 손님이 방문하지 않는 경우 패널티가 1 증가하고, 가게의 문이 닫혀 있는 동안 손님이 방문하는 경우 역시 패널티가 1 증가한다.

이 때 패널티를 가장 적게 받을 수 있는 폐점 시간 중 가장 이른 시간을 구하는 문제이다.

 

먼저 각 시간대의 방문 여부를 구하기 위해 문자열을 배열로 분리한다.

// 방문 로그를 분리
char[] visited = customers.toCharArray();

 

그리고 각 시간대의 패널티, 최소 패널티, 최적 폐점 시간을 저장할 변수를 선언한다.

// 패널티
int penalty = 0;
// 최소 패널티
int minPenalty = 0;
// 최적 폐점 시간
int optimalClosingTime = 0;

 

각각의 방문 로그를 탐색하는데 i번째 시간마다 폐점을 한다고 가정하고 패널티를 계산한다.
i번째의 방문 여부가 'Y'인 경우 열려있는 동안 손님이 방문한 경우이므로 패널티를 감소하고,
i번째의 방문 여부가 'N'인 경우 열려있는 동안 손님이 방문하지 않은 경우이므로 패널티를 증가한다.
현재 패널티가 최소 패널티보다 작은 경우에는 최소 패널티와 최적 폐점 시간을 갱신해준다.
단 탐색이 0번 인덱스부터 시작하였으므로 실제 'i번째' 에 해당하는 시간은 i + 1로 계산한다.

for(int i = 0; i < visited.length; i++) {
    // i번째의 방문여부가 'Y'인 경우 패널티 감소
    if(visited[i] == 'Y') penalty--;
    // i번째의 방문여부가 'N'인 경우 패널티 증가
    else penalty++;

    // 현재 패널티가 최소 패널티보다 작은 경우
    // 최소 패널티 및 최적 폐점 시간 갱신
    if(penalty < minPenalty) {
        minPenalty = penalty;
        optimalClosingTime = i + 1;
    }
}

 

최종적으로 구해진 최소 패널티의 시간대를 return 한다.

// 최소 패널티의 시간을 return
return optimalClosingTime;

---

최종 코드

class Solution {
    public int bestClosingTime(String customers) {
        // 방문 로그를 분리
        char[] visited = customers.toCharArray();
        // 패널티
        int penalty = 0;
        // 최소 패널티
        int minPenalty = 0;
        // 최적 폐점 시간
        int optimalClosingTime = 0;
        
        for(int i = 0; i < visited.length; i++) {
            // i번째의 방문여부가 'Y'인 경우 패널티 감소
            if(visited[i] == 'Y') penalty--;
            // i번째의 방문여부가 'N'인 경우 패널티 증가
            else penalty++;
            
            // 현재 패널티가 최소 패널티보다 작은 경우
            // 최소 패널티 및 최적 폐점 시간 갱신
            if(penalty < minPenalty) {
                minPenalty = penalty;
                optimalClosingTime = i + 1;
            }
        }
        
        // 최소 패널티의 시간을 return
        return optimalClosingTime;
    }
}

---