2026-10-09
count_phases.c
#include <stddef.h>
size_t count_phases(const char *queue) {
}
読み書きロックへの要求を到着順に並べた文字列 queue を受け取り、ロックが何回に分けて許可を出すかを返す count_phases を書いてください。'R' は読み取り、'W' は書き込みの要求です。ロックは到着順を守り、続けて並んだ読み取りは1回でまとめて通し、書き込みは1つずつ通します。書き込みより後に来た読み取りが、その書き込みを追い越すことはありません。queue が空なら 0 を返します。
入力例 1
count_phases("RRWRR")
出力例 1
3
入力例 2
count_phases("RWWRRR")
出力例 2
4
入力例 3
count_phases("")
出力例 3
0
Reference
#include <assert.h>
#include <stddef.h>
size_t count_phases(const char *queue) {
size_t phases = 0;
for (size_t i = 0; queue[i]; i++)
if (queue[i] == 'W' || i == 0 || queue[i - 1] == 'W')
phases++;
return phases;
}
参考実装は queue を先頭から1文字ずつ見て、新しい許可が始まる文字を数えます。新しい許可が始まるのは、書き込みの要求か、先頭にある読み取りか、書き込みの直後に来た読み取りです。読み取りの直後の読み取りは前と同じ回に通るので、数えません。
"RRWRR" では、先頭の R、真ん中の W、その直後の R の3か所で新しい許可が始まります。最後の2つの読み取りは、先頭の2つとの間に書き込みがあるので、同じ回には入れません。もし後の2つを先頭の回に混ぜて読み取りを優先すれば2回で済みますが、その分だけ書き込みは後回しになり、読み取りが途切れなく来る限り入れなくなります。到着順を守れば、書き込みは自分より前の要求が済んだ時点で必ず順番が来ます。
|| は左から順に評価し、真になった時点で残りを評価しないので、i == 0 のときに queue[i - 1] を読むことはありません。掲載したのは参考実装で、唯一の正解ではありません。直前の要求の種類を変数に覚えておき、書き込みのときと、読み取りが書き込みの後に来たときに数える書き方でも同じ結果になります。