2147. Number of Ways to Divide a Long Corridor

• 복도에 의자 S 와 화분 P 이 있을 때 벽을 세워서 각 공간에 의자 2개가 포함되도록 나누는 경우의 수를 구한다.

• 먼저 양 끝에 화분이 있다면 제외시킨다. 어차피 양끝에 있는 화분 사이에는 벽을 세우기 어려우므로 미리 제외시키면 문제를 단순화 할 수 있다.

• 이렇게 얻어진 시작점 pos 과 끝점 end을 기준으로 시작점을 움직이면서 칸막이를 세우는 경우의 수를 계산한다.
• 칸막이는 자리가 2개가 되는 시점마다 세울 수 있다.
• 단, 자리가 2개가 되지 않았는데 화분이 등장한다면 해당 위치에는 칸막이를 세울수 없으므로 무시한다.
• 만일 자리가 2개가 되지 못한 상태에서 복도가 끝난다면 공간을 나눌 수 없으므로 경우의 수는 없는 것이 된다.
• 만약 자리가 2개가 되는 시점 바로 뒤에 화분이 없다면 칸막이를 세울 수 있다. 이때 경우의 수는 1개 뿐이다.
• 만약에 자리가 2개가 되는 시점 이후에 화분이 존재한다면 연속되는 화분의 개수 + 1 만큼 칸막이를 세우는 경우의 수가 생긴다.
• 예를 들어 SSPPSS 와 같은 경우 SS|PPSS SSP|PSS SSPP|SS 와 같이 세가지 경우의 수로 칸막이를 세울 수 있다.
• 전체 경우의 수는 칸막이를 세울 수 있는 지점 마다의 경우의 수를 곱한 것이 된다.

class Solution {
public:
    static constexpr int MOD = 1e9 + 7;
    int numberOfWays(string corridor) {
        int end = corridor.length() - 1;
        int pos = 0;
        int seats = 0;
        int plants = 0;
        long long result = 1;
        // skip first & last plants
        while (pos <= end) {
            if (corridor[pos] == 'P') ++pos;
            else break;
        }
        while (end >= pos) {
            if (corridor[end] == 'P') --end;
            else break;
        }
        while (pos <= end) {
            // count seats
            seats = 0;
            while (pos <= end && seats != 2) {
                if (corridor[pos] == 'S') ++seats;
                ++pos;
            }
            // cannot make 2 seats, so break the loop
            if (seats != 2) break;
            // count plants
            plants = 0;
            while (pos <= end) {
                if (corridor[pos] != 'P') break;
                ++pos; ++plants;
            }
            result = (result * (plants + 1)) % MOD;
        }
        // cannot make room with 2 seats
        return seats == 2? result : 0;
    }
};