1. 문제 소개

2483. Minimum Penalty for a Shop

2. 나의 풀이

prefix와 suffix를 사용해 풀었다.
시간복잡도는 $O(n)$이다.

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        n = len(customers)                                # 전체 시간 슬롯 개수
        prefix = [0] * (n + 1)                            # prefix[i]: customers[0:i]에서 'N'의 개수
        suffix = [0] * (n + 1)                            # suffix[i]: customers[i:n]에서 'Y'의 개수

        for i in range(n):                                # 왼쪽에서 오른쪽으로 스캔
            prefix[i + 1] = prefix[i] + (1 if customers[i] == "N" else 0)
                                                          # 이전까지의 'N' 누적 + 현재가 'N'이면 1 증가

        for i in range(n - 1, -1, -1):                    # 오른쪽에서 왼쪽으로 스캔
            suffix[i] = suffix[i + 1] + (1 if customers[i] == "Y" else 0)
                                                          # 이후 구간의 'Y' 누적 + 현재가 'Y'이면 1 증가

        ans = 0                                           # 최소 벌점을 만드는 닫는 시간
        best = prefix[0] + suffix[0]                      # i=0(처음부터 닫음)일 때의 벌점

        for i in range(1, n + 1):                         # 모든 가능한 닫는 시간 i 검사
            cur = prefix[i] + suffix[i]                   # 현재 닫는 시간 i의 벌점 계산
            if cur < best:                                # 더 작은 벌점을 발견하면
                best = cur                                # 최소 벌점 갱신
                ans = i                                   # 해당 닫는 시간 기록

        return ans                                        # 최소 벌점을 만드는 닫는 시간 반환

3. 다른 풀이

실제로 합을 구하지 않고 벌점을 줄이는 방식을 적용해 한 번의 반복만으로 구현해내었다.
같은 시간복잡도이지만 훨씬 빠르다.

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        bestTime = 0            # 최소 벌점을 만드는 닫는 시간(결과)
        minPenalty = 0          # 현재까지의 최소 벌점
        prefix = 0              # 누적 벌점 변화값

        for i in range(len(customers)):
            # 현재 시간을 열어두는 쪽으로 한 칸 이동한다고 생각
            # 'Y'면: 닫아서 놓칠 벌점 1이 사라지므로 -1
            # 'N'면: 열어두고 손님이 없으므로 벌점 1 증가
            prefix += -1 if customers[i] == 'Y' else 1

            # 누적 벌점이 더 작아지는 지점이
            # 곧 최소 벌점을 만드는 닫는 시간 후보
            if prefix < minPenalty:
                bestTime = i + 1    # i번째 이후에 닫음
                minPenalty = prefix

        return bestTime             # 최소 벌점이 되는 닫는 시간 반환

4. 마무리

prefix와 suffix를 사용해서 좋았다.