[LeetCode] 2147. Number of Ways to Divide a Long Corridor

https://leetcode.com/problems/number-of-ways-to-divide-a-long-corridor/description/

Number of Ways to Divide a Long Corridor - LeetCode

leetcode - Number of Ways to Divide a Long Corridor

문제 유형 : 수학, 다이나믹 프로그래밍, 조합, 투 포인터, 슬라이딩 윈도우

문제 난이도 : Hard

 

문제

Along a long library corridor, there is a line of seats and decorative plants. You are given a 0-indexed string corridor of length n consisting of letters 'S' and 'P' where each 'S' represents a seat and each 'P' represents a plant.

One room divider has already been installed to the left of index 0, and another to the right of index n - 1. Additional room dividers can be installed. For each position between indices i - 1 and i (1 <= i <= n - 1), at most one divider can be installed.

Divide the corridor into non-overlapping sections, where each section has exactly two seats with any number of plants. There may be multiple ways to perform the division. Two ways are different if there is a position with a room divider installed in the first way but not in the second way.

Return the number of ways to divide the corridor. Since the answer may be very large, return it modulo 10⁹ + 7. If there is no way, return 0.

 

긴 도서관의 복도가 있다. 일렬로 좌석과 데코용 식물이 있다.

당신은 n의 길이의 문자열 corridor를 받고, 'S'는 좌석, 'P'는 식물을 의미한다.

 

하나의 파티션은 인덱스 0의 왼쪽에, 또 하나는 인덱스 n-1의 오른쪽에 있다.

당신은 파티션을 추가하여 각 섹션별로 좌석이 두 개씩 있도록 나누어야 한다. 

다양한 방법이 있을 수 있다.

이 복도를 분할하는 모든 경우의 수를 구하여라. 답이 커질 수 있으니, 1e9 + 7로 나눈 나머지를 반환하라.

방법이 없다면, 0을 반환하라.

 

 

풀이

두 쌍의 좌석들 간의 파티션을 두는 경우의 수는 오른쪽 쌍의 첫 번째 좌석의 인덱스 - 왼쪽 쌍의 두 번째 좌석의 인덱스이다.

인접한 두 쌍들끼리의 각각의 경우의수들을 구해서 모두 곱해주면 된다.

 

불가능한 경우는 두 가지 있다.

의자가 홀수인 경우와, 의자가 한 개도 없는 경우이다.

 

슬라이딩 윈도우 / 투 포인터 기법을 이용해서 두 좌석페어간의 거리들을 모두 곱해주면 된다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();
using ll = long long;
class Solution {
public:
    int numberOfWays(string corridor) {
        int n = corridor.size();
        int MOD = 1e9 + 7;
        
        int cnt = 0;
        int streak = 0;
        ll ans = 1; 
        int len = 0;
        for(int i = 0; i < n; i++) {
            if(corridor[i] == 'S') {
                streak++;
                cnt++;
                if(streak >= 2) {
                    int j = i+1;
                    while(j < n && corridor[j] == 'P') {
                        j++;
                    }
                    if(j < n) ans = (ans * (j-i)) % MOD;
                    streak = 0;
                    i = j-1;
                }
            }
        }

        if(cnt%2 || cnt == 0) return 0;
        return ans;
    }
};

 

Go

const MOD int = 1_000_000_007
func numberOfWays(corridor string) int {
    n := len(corridor)
    ans := 1

    streak := 0
    cnt := 0
    for i := 0; i < n; i++ {
        if corridor[i] == 'S' {
            streak++
            cnt++
            if streak >= 2 {
                j := i+1
                for j < n && corridor[j] == 'P' {
                    j++
                }
                if j < n {
                    ans = (ans * (j-i)) % MOD
                }
                streak = 0
                i = j-1
            }
        }
    }

    if cnt%2 == 1 || cnt == 0 {
        return 0
    }

    return ans
}

 

Rust

impl Solution {
    pub fn number_of_ways(corridor: String) -> i32 {
        let MOD :i64 = 1_000_000_007;
        let bs = corridor.as_bytes();
        let n = corridor.len();
        let mut ans = 1i64;

        let mut streak = 0;
        let mut cnt = 0;
        for i in 0..n {
            if bs[i] == b'S' {
                streak += 1;
                cnt += 1;
                if streak >= 2 {
                    let mut j = i+1;
                    while j < n && bs[j] == b'P' {
                        j += 1;
                    }
                    if j < n {
                        ans = (ans * (j - i) as i64) % MOD;
                    }
                    streak = 0;
                }
            }
        } 

        if cnt % 2 == 1 || cnt == 0 {
            return 0
        }

        ans as i32
    }
}