Paiza 長テーブルのうなぎ屋
練習問題の「長テーブルのうなぎ屋」を解きました。
言語はJavaです。
練習問題については解答を公開してもいいらしいのでここに載せます。
【問題の簡単な説明】
店には輪状に並べた席があり、グループのお客さんを指定の席から時計回りに座らせていきます。(席には1から順に番号が振られています。)ただし、座らせていく途中に、一つでも他のグループの人が座っていた席があったら全員帰ってしまうそうです。結果的に何人が店に座るのかを回答として出力します。
【個人的考え・解答】
リンクリストっぽい。
輪状に並べた人が座っているかチェックする部分が一番の肝ですね。
席が空いているかを保存するのに配列を使い、座る位置を添え字で表すようにしました。
配列要素の値が0なら空席で、1ならすでに人がいる席です。
座る位置番号が一周したら0番に戻すように、以下のように席の数の剰余を使っています。(iの初期値は座り始める位置としています)
seats[i % num_of_seats]
(正しい座る位置) = {(スタート位置+何人目)で求めた仮の座る位置} % (席の数)
【コード全体】
import java.util.*;
public class Main {
private static int seats; ///< 席情報 0:空席 1:すでに人がいる
private static int num_of_seats; ///< 席の数
// 座れるかチェックし、席状態を更新する関数
public static boolean sit(int num, int start_pos) {
// 座れるか人数分チェック
for (int i = start_pos; i < (num + start_pos); i++ ) {
if (seats[i % num_of_seats] == 1) {
//すでに人がいた
return false;
}
}
// 座らせていく処理
for (int i = start_pos; i < (num + start_pos); i++ ) {
seats[i % num_of_seats] = 1;
}
return true;
}
// 座っている人の数を数える関数
public static int count_sitting_person() {
// 結果用変数
int count = 0;
// for inで座っている人を数える
for (int e : seats) {
if (e == 1) {
++count;
}
}
return count;
}
public static void main(String args) {
// 読み取り準備
Scanner sc = new Scanner(System.in);
// 読み取り
num_of_seats = sc.nextInt();
int num_of_groups = sc.nextInt();
// 店に席を作る
seats = new int[num_of_seats];
for (int e : seats) {
e = 0;
}
// お客さんの処理
for ( int i = 0; i < num_of_groups; i++) {
int a_i, b_i;
a_i = sc.nextInt(); // 人数
b_i = sc.nextInt(); // 座り始める場所
// 座れるかチェック
sit(a_i, b_i);
}
// 座れている人数の計算
int num_of_sitting_person = count_sitting_person();
// 結果出力
System.out.println(num_of_sitting_person);
}
}
まだまだ改善点はあるでしょうが、素直にコード化するならこのような感じになると思います。