Paizaの長テーブルのうなぎ屋を解決する

Qiitaの記事:Javaで解いてみた!! Paiza練習問題「長テーブルのうなぎ屋」

を見て、そういえば僕も前にうまく解けずに投げ出してしまった事を思い出しました。

java学習開始から1年半たっていて、今なら解けるんじゃないかと思って再挑戦しました。

はじめに

この記事では、ネタばれを含みます。

ご覧になる際は、あらかじめご了承ください。

結果

無事クリアできました。

提出したコード

全量は、過去分も含めてgitに置いてあります

package src.main;

import java.util.Scanner;

/**
 * paizaの長テーブルのうなぎ屋の解法
 * 

 * クラス名を[Main]に変更すれば、そのまま提出可能
 * @author Naoto Wada
 *
 */
public class UnagiStore {

    /**
     * paiza用のメイン関数
     * @param args
     */
    public static void main(String[] args) {

        int result = 0;
        try (Scanner sc = new Scanner(System.in)) {
            String tableAndParties = sc.nextLine();
            int capacity = Integer.parseInt(tableAndParties.split(" ")[0]);
            int parties = Integer.parseInt(tableAndParties.split(" ")[1]);

            int[][] groups = createGroups(sc, parties);

            result = execute(capacity, groups);
        }
        System.out.println(result);
    }

    private static int[][] createGroups(Scanner sc, int parties) {
        int[][] groups = new int[parties][2];
        for (int i = 0; i < parties; i++) {
            String[] groupAndPosition = sc.nextLine().split(" ");
            groups[i][0] = Integer.parseInt(groupAndPosition[0]);
            groups[i][1] = Integer.parseInt(groupAndPosition[1]);
        }
        return groups;
    }

    /**
     * 実行関数.
     * 

     * 座席数と入力グループの情報から顧客を着席させる.
     *
     * @param capacity 座席数
     * @param groups 入力グループ情報
     * @return 着席数
     */
    public static int execute(int capacity, int[][] groups) {

        Chairs chair = new UnagiStore().new Chairs(capacity);

        for (int grpCnt = 0; grpCnt < groups.length; grpCnt++) {

            int customers = groups[grpCnt][0];
            int position = groups[grpCnt][1];

            chair.occupyIfAvailable(customers, position);
        }
        return chair.countOccupied();
    }

    /**
     * 座席管理クラス
     * 

     * 指定した座席に客が座れるかどうかを管理し、着席可能な場合のみ席を確保する.
     * 指定値を超えた場合でも、エラーとはならずに単純に着席を行わない
     * @author Naoto Wada
     *
     */
    public class Chairs {
        private boolean[] chairs;

        public Chairs(int capacity) {
            this.chairs = new boolean[capacity];
        }

        /**
         * 座席の着席数をカウントする.
         * 

         * 全てが空席だった場合は[0]を返却する.
         * @return 着席数
         */
        public int countOccupied() {
            int occupied = 0;
            for (boolean sut : chairs) {
                if (sut) {
                    occupied++;
                }
            }
            return occupied;
        }

        /**
         * 指定された座席から顧客が着席できるかを判定した後着席させる.
         * 

         * 指定した座席が全席数を超えている場合は着席させない.
         * 例えば、席数:4, 客数x, 指定席5
         * 

         * 顧客が連番で座れない場合は着席させない.
         * 例えば、席数:4, グループ1[客2, 指定席1], グループ2[客2, 指定席2]
         * @param customers 客数
         * @param position 指定席
         */
        public void occupyIfAvailable(int customers, int position) {

            if (hasAlreadyOccupied(customers, position)) {
                return;
            }
            occupySeat(customers, position);
        }

        private boolean hasAlreadyOccupied(int customers, int position) {
            int posit = position - 1;
            for (int i = 0; i < customers; i++) {
                if (chairs[posit % chairs.length]) {
                    return true;
                }
                posit++;
            }
            return false;
        }

        private void occupySeat(int customers, int position) {
            int posit = position - 1;
            for (int i = 0; i < customers; i++) {
                chairs[posit % chairs.length] = true;
                posit++;
            }
        }

    }
}

テストも書いてみた

package src.test;

import static org.hamcrest.CoreMatchers.*;
import static org.junit.Assert.*;

import org.junit.Test;

import src.main.UnagiStore;

public class EelShopTest {

    @Test
    public void test_6人テーブルに3名と1名と2名がそれぞれ席を指定した場合は最初の2グループだけ全員が座れる() {
        // paizaの例1
        int table = 6;
        int[][] groupA = new int[][] { { 3, 2 }, { 1, 6 }, { 2, 5 } };
        int result = UnagiStore.execute(table, groupA);
        assertThat(result, is(4));
    }

    @Test
    public void test_12人テーブルに4名ずつの6グループが席を指定した場合は全席分埋まって座れないグループがある() {
        // paizaの例2
        int table = 12;
        int[][] group = new int[][] { { 4, 6 }, { 4, 8 }, { 4, 10 }, { 4, 12 }, { 4, 2 }, { 4, 4 } };
        int result = UnagiStore.execute(table, group);
        assertThat(result, is(12));
    }
}

何に気を付ければ良いのか

今回の問題を現実的に捉える場合、”長テーブル”といいつつ”円卓”のような問題です。

色々な方が仰っていますが、境界値の扱いが大事です。

テーブルの最後の席(以下図だと3番目)から、最初の席(以下図だと1番目)に戻る

という処理をどうコードで実現するのかがになります。

解き方としては指定席位置から最大席数で割った余りを使うと良いです。

:指定席位置÷最大席数=本当の指定席

配列の場合、初期位置は0なので、指定席は-1して処理すればよいと思います。

例)指定席:3, 最大席数:3

 →3-1 / 3 = 2要素目

例)指定席:1, 最大席数:3

 →1-1 / 3 = 0要素目

円卓とか言ってる割りに、図が長テーブルっぽくなっているのは単なるイメージの問題です。

現実の問題とコーディングの問題はまた別なのです。

ちなみに、上記コードの[hasAlreadyOccupied]がその処理にあたります。

過去に作成したコード

前項で記載した、境界値の操作がうまくできていません。

最大値を跨ぐ処理を行う場合、以下では

java.lang.ArrayIndexOutOfBoundsExceptionが発生してしまいます。

エラーとなる入力例)

3 1

2 3

 
package src.main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class OldUnagiStore {

    private enum TERMS {

        /** 座席数"0" .*/
        SEAT(0),
        /** グループ数"1" .*/
        GROUP(1),
        /** グループ数"0" .*/
        MEMBER(0),
        /** グループ数"1" .*/
        START(1),
        ;
        /** 入力位置 .*/
        private int numberOfType;

        /**
         * TERMSコンストラクタ
         * @param numberOfType
         *      入力位置
         */
        TERMS(int numberOfType) {
            this.numberOfType = numberOfType;
        }
    }

    public static void main(String[] args) {

        try (BufferedReader input = new BufferedReader(new InputStreamReader(System.in))) {

            String inputTerm = input.readLine();

            //座席数とグループ数の取得
            int seat = Integer.parseInt(inputTerm.split(" ")[TERMS.SEAT.numberOfType]);
            int group = Integer.parseInt(inputTerm.split(" ")[TERMS.GROUP.numberOfType]);

            //グループ人数と座席開始位置の取得
            int[] member = new int[group];
            int[] start = new int[group];

            //グループ人数と座席開始位置の入力
            for (int i = 0; i < group; i++) {

                String record = input.readLine();
                member[i] = Integer.parseInt(record.split(" ")[TERMS.MEMBER.numberOfType]);
                start[i] = Integer.parseInt(record.split(" ")[TERMS.START.numberOfType]);
            }

            //座席の設定
            int[] result = new int[seat];

            //グループの件数分ループ
            for (int grpCnt = 0; grpCnt < group; grpCnt++) {

                //スタート位置をフラグ化
                int startF = result[start[grpCnt]] - 1;

                //グループ内人数分ループ
                for (int mbrCnt = 0; mbrCnt < member[grpCnt]; mbrCnt++) { //挿入位置をフラグ化 int insertF = (start[grpCnt] - 1 + mbrCnt); //①スタート位置から終点までが一度に収まる場合 if (result.length > startF + member[grpCnt]) {

                        if (!(insertF == result.length)) {
                            //スタート位置に値がない場合
                            if (result[insertF] == 0) {

                                result[insertF] = 1;
                                continue;
                            }
                        }
                    }
                    //②スタート位置から最大値を超えていく場合
                    int overLength = insertF - member[grpCnt];
                    if (insertF == result.length) {

                        //②-1最大数を超えない値域
                        if (result[overLength] == 0) {

                            result[overLength] = 1;
                            continue;
                        }
                        //②-2最大数を超えた値域
                        else if (result[overLength - insertF] == 0) {

                            result[overLength - insertF] = 1;
                            continue;
                        }
                    }

                }
            }

            //値の計算
            int amount = 0;
            for (int res : result) {

                amount += res;
            }

            System.out.println(amount);

        } catch (IOException exp) {
            throw new IllegalArgumentException("入力値不正");
        }
    }
}

Object指向で書くにはどうすべきか

これについては、before/afterで記載したいと思います。

なので、別記事にまとめる予定です。

→[2018/11/24]まとめました

ウナギって英語で?

Eelっていう見たいです。

クラス宣言するときUnagiかEelでちょっと迷いました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする