1. 문제 소개

2147. Number of Ways to Divide a Long Corridor

2. 나의 풀이

의자의 개수가 홀수거나 없는 경우 등의 엣지 케이스를 제외하고, 짝수인 경우만 계산한다.
이때 경우의 수에 더하는 것이 아니라 곱하는 것이 포인트였다.
시간복잡도는 $O(n)$이다.

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        MOD = 10**9 + 7              # 결과를 나눌 모듈러 값
        
        ans = 1                     # 가능한 분할 방법의 누적 곱
        cnt = 0                     # 지금까지 센 좌석(S)의 개수
        temp = 0                    # 현재 좌석 쌍 이후에 등장한 문자 수(P 포함)
        
        # 복도를 왼쪽부터 한 칸씩 순회
        for c in corridor:
            if c == "S":
                cnt += 1            # 좌석을 만나면 좌석 개수 증가
            
            # 좌석이 짝수 개(2, 4, 6, ...)가 되었고,
            # 현재 쌍(2개 좌석) 이후의 구간을 처리 중인 경우
            if cnt >= 2 and cnt % 2 == 0:
                if c == "P":
                    temp += 1       # 화분(P)이면 분할 후보 간격 증가
                else:
                    # 좌석(S)을 만난 경우:
                    # 이전 좌석 쌍과 현재 좌석 사이에 분할 가능 위치가 temp개 존재
                    temp += 1
                    ans = (ans * temp) % MOD  # 경우의 수에 곱해줌
                    temp = 0        # 다음 좌석 쌍을 위해 초기화
        
        # 좌석이 정확히 2개뿐이면 분할할 필요가 없으므로 경우의 수는 1
        if cnt == 2:
            return 1
        # 좌석 개수가 홀수이거나 아예 없는 경우는 분할 불가능
        elif cnt % 2 == 1 or cnt == 0:
            return 0

        # 모든 조건을 만족한 경우 누적된 경우의 수 반환
        return ans

3. 다른 풀이

Editorial의 풀이는 너무 복잡하고, 간단한 풀이들은 내 풀이와 같은 방식이었다.

4. 마무리

간단하게 풀어서 기분이 좋다.