【Java】PaizaのBランク問題を解いてみた

はじめに

スキルチェック過去問題集（Java編）から「日別訪問者数の最大平均区間 (paizaランクB相当)」を解いてみました
プログラム初心者ですが、アルゴリズムの部分もわかりやすくまとめてみました！
ちなみに筆者は実務未経験のBランクです。。

【問題のリンク】
https://paiza.jp/works/mondai/skillcheck_archive/max_range?language_uid=java

目次

• 問題
• 解き方の流れ
• 解答コード

問題

問題文

あなたは、とあるウェブサイトを管理していました。
ある連続したk日間、このウェブサイトでキャンペーンを行ったのですが、いつからいつまでの期間に行ったかを忘れてしまいました。

幸い、ウェブサイトを運営していた全n日分のアクセスログが残っており、1日ごとの訪問者数が分かっています。
とりあえず、連続するk日の中で、1日あたりの平均訪問者数が最も多い期間を、キャンペーンを行った期間の候補だと考えることにしました。

n日分の訪問者数のリストとキャンペーンの日数kが入力されるので、キャンペーンを行った期間の候補数と、候補の中で最も早い開始日を出力してください。

---

入力される値

入力は2行から成ります。
1行目にはnとkが半角スペース区切りで入力されます。
2行目にはn個の整数a_1, a_2, …, a_nが半角スペース区切りで入力されます。a_iはi日目の訪問者数を表します。

---

期待する出力

キャンペーンを行った期間の候補数と、候補の中で最も早い開始日を、この順で半角スペース区切りで1行で出力してください。

---

条件

すべてのテストケースにおいて、以下の条件をみたします。
・1≦n≦1,000
・1≦k≦n
・0≦a_i≦100

---

入力例1

5 3
1 2 3 2 1

出力例1

1 2

入力例2

10 2
6 2 0 7 1 3 5 3 2 6

出力例2

5 1

詳細はこちらから問題を確認してみてください！

解き方の流れ

1.大まかな流れを考える

普段はコメントアウトで大まかな流れを書いてから、コードを書いています。
今回はわかりやすいように図で描いてみました！

2.コードを書いてみる

大まかな流れを考えたらコードを書いてみます。
各工程に沿ってコードを書いていきます。スコープが長くなりそうなところはメソッドに分けるようにしています。

---

①入力1

標準入力はScannerクラスを使用します。

PaizaB01Visitors.java

    // 入力
    Scanner sc = new Scanner(System.in);
    // アクセスログが残っていた日数n
    int n = sc.nextInt();
    // キャンペーンを行った日数k
    int k = sc.nextInt();

---

②入力2

メソッドに分けます。
まずは配列の初期化、メソッドの呼び出しを記述します。↓

PaizaB01Visitors.java

    // n日間の訪問者数配列
    int[] visitorCount = new int[n];
    // 訪問者の数を入力（n日分）
    visitorCount = inputVisitor(n, visitorCount, sc);

次にメソッドの中身を書いていきます。↓

PaizaB01Visitors.java

    /** 
     * 訪問者の数を入力するメソッド（n日分）
     * @param n アクセスログが残っていた日数n
     * @param visitorCount n日間の訪問者数配列
     * @param sc 標準入力
     * @return 訪問者数を入力した配列
     */
    private static int[] inputVisitor(int n, int[] visitorCount, Scanner sc) {
        for(int i = 0; i < n; i++) {
            visitorCount[i] = sc.nextInt();
        }
        return visitorCount;
    }

---

③k日間の訪問者合計値の配列を作る

メソッドに分けます。
まずは配列の初期化、メソッドの呼び出しを記述します。↓

PaizaB01Visitors.java

    // k日間分の訪問者合計数の配列[n - k + 1]
    int[] visitorSumCount = new int[n - k + 1];
    // visitorSumCountを算出する
    visitorSumCount = visitorSum(visitorCount, n, k, visitorSumCount);

次にメソッドの中身を書いていきます。↓

PaizaB01Visitors.java

    /** 
         * k日間分の訪問者合計を求める((n - k + 1)回分)
     * @param visitorCount n日間の訪問者数配列
     * @param n アクセスログが残っていた日数n
     * @param k キャンペーンを行った日数k
     * @param visitorSumCount k日間分の訪問者合計数の配列
     * @return k日間分の訪問者合計数を算出した配列
     */
    private static int[] visitorSum(int[] visitorCount, int n, int k, int[] visitorSumCount) {
        for(int i = 0; i < (n - k + 1); i++) {
            for(int j = i; j < (k + i); j++) {
                visitorSumCount[i] += visitorCount[j];
            }
        }
        return visitorSumCount;
    }

---

④訪問者合計値の中でMax値を求める

メソッドに分けます。
まずは変数の初期化、メソッドの呼び出しを記述します。↓

PaizaB01Visitors.java

    // visitorSumCountの中でMaxの値
    int visitorSumMax = 0;
    // visitorSumMaxを求める
    visitorSumMax = sortVisitorSumMax(visitorSumCount, visitorSumMax);

次にメソッドの中身を書いていきます。↓

PaizaB01Visitors.java

    /**
     * 訪問者合計値の中でMax値を求める
     * @param visitorSumCount k日間分の訪問者合計数の配列
     * @param visitorSumMax visitorSumCount中のMax値
     * @return 求めたMax値
     */
    private static int sortVisitorSumMax(int[] visitorSumCount, int visitorSumMax) {
        for(int i = 0; i < visitorSumCount.length; i++) {
            if(visitorSumCount[i] > visitorSumMax) {
                visitorSumMax = visitorSumCount[i];
            }
        }
        return visitorSumMax;
    }

---

⑤訪問者合計配列の中でMax値になるインデックス値をリストに入れる

PaizaB01Visitors.java

    // visitorSumMaxになるindex値を入れたリスト
    List<Integer> visitorSumMaxStartDay = new ArrayList<>();
    // visitorSumMaxStartDayを求める
    visitorSumMaxStartDay = visitorSumMaxStartDaySort(visitorSumCount, visitorSumMax, visitorSumMaxStartDay);

次にメソッドの中身を書いていきます。↓

PaizaB01Visitors.java

    /**
     * visitorSumCountの中でvisitorSumMaxになるインデックスをリストに保存する
     * @param visitorSumCount k日間分の訪問者合計数の配列
     * @param visitorSumMax visitorSumCount中のMax値
     * @param visitorSumMaxStartDay visitorSumCountの中でvisitorSumMaxになるインデックス
     * @return インデックスが入ったリストを返す
     */
    private static List<Integer> visitorSumMaxStartDaySort(int[] visitorSumCount, int visitorSumMax, List<Integer> visitorSumMaxStartDay) {
        for(int i = 0; i < visitorSumCount.length; i++) {
            if(visitorSumCount[i] == visitorSumMax) {
                visitorSumMaxStartDay.add(i);
            }
        }
        return visitorSumMaxStartDay;
    }

---

⑥出力

これで最後です！
visitorSumMaxStartDayリストの要素数とインデックス(0)+ 1の値を出力します。

PaizaB01Visitors.java

    // 候補日の数を出力
    System.out.print(visitorSumMaxStartDay.size() + " ");
    // 候補日の最初の日を出力
    System.out.print(visitorSumMaxStartDay.get(0) + 1);

解答コード

最後に解答コードを載せます！

PaizaB01Visitors.java

import java.util.*;

public class PaizaB01Visitors {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        // アクセスログが残っていた日数n
        int n = sc.nextInt();
        // キャンペーンを行った日数k
        int k = sc.nextInt();

        // n日間の訪問者数配列
        int[] visitorCount = new int[n];
        // 訪問者の数を入力（n日分）
        visitorCount = inputVisitor(n, visitorCount, sc);

        // k日間分の訪問者合計数の配列[n - k + 1]
        int[] visitorSumCount = new int[n - k + 1];
        // visitorSumCountを算出する
        visitorSumCount = visitorSum(visitorCount, n, k, visitorSumCount);

        // visitorSumCountの中でMaxの値
        int visitorSumMax = 0;
        // visitorSumMaxを求める
        visitorSumMax = sortVisitorSumMax(visitorSumCount, visitorSumMax);

        // visitorSumMaxになるindex値を入れたリスト
        List<Integer> visitorSumMaxStartDay = new ArrayList<>();
        // visitorSumMaxStartDayを求める
        visitorSumMaxStartDay = visitorSumMaxStartDaySort(visitorSumCount, visitorSumMax, visitorSumMaxStartDay);

        // 候補日の数を出力
        System.out.print(visitorSumMaxStartDay.size() + " ");
        // 候補日の最初の日を出力
        System.out.print(visitorSumMaxStartDay.get(0) + 1);

        sc.close();
    }

    /**
     * 訪問者の数を入力するメソッド（n日分）
     * @param n アクセスログが残っていた日数n
     * @param visitorCount n日間の訪問者数配列
     * @param sc 標準入力
     * @return 訪問者数を入力した配列
     */
    private static int[] inputVisitor(int n, int[] visitorCount, Scanner sc) {
        for(int i = 0; i < n; i++) {
            visitorCount[i] = sc.nextInt();
        }
        return visitorCount;
    }

    /**
     * k日間分の訪問者合計を求める((n - k + 1)回分)
     * @param visitorCount n日間の訪問者数配列
     * @param n アクセスログが残っていた日数n
     * @param k キャンペーンを行った日数k
     * @param visitorSumCount k日間分の訪問者合計数の配列
     * @return k日間分の訪問者合計数を算出した配列
     */
    private static int[] visitorSum(int[] visitorCount, int n, int k, int[] visitorSumCount) {
        for(int i = 0; i < (n - k + 1); i++) {
            for(int j = i; j < (k + i); j++) {
                visitorSumCount[i] += visitorCount[j];
            }
        }
        return visitorSumCount;
    }

    /**
     * 訪問者合計値の中でMax値を求める
     * @param visitorSumCount k日間分の訪問者合計数の配列
     * @param visitorSumMax visitorSumCount中のMax値
     * @return 求めたMax値
     */
    private static int sortVisitorSumMax(int[] visitorSumCount, int visitorSumMax) {
        for(int i = 0; i < visitorSumCount.length; i++) {
            if(visitorSumCount[i] > visitorSumMax) {
                visitorSumMax = visitorSumCount[i];
            }
        }
        return visitorSumMax;
    }

    /**
     * visitorSumCountの中でvisitorSumMaxになるインデックスをリストに保存する
     * @param visitorSumCount k日間分の訪問者合計数の配列
     * @param visitorSumMax visitorSumCount中のMax値
     * @param visitorSumMaxStartDay visitorSumCountの中でvisitorSumMaxになるインデックス
     * @return インデックスが入ったリストを返す
     */
    private static List<Integer> visitorSumMaxStartDaySort(int[] visitorSumCount, int visitorSumMax, List<Integer> visitorSumMaxStartDay) {
        for(int i = 0; i < visitorSumCount.length; i++) {
            if(visitorSumCount[i] == visitorSumMax) {
                visitorSumMaxStartDay.add(i);
            }
        }
        return visitorSumMaxStartDay;
    }
}

おわりに

ここまで見て頂き、ありがとうございました！
何かご意見や改善箇所などありましたら、コメント頂けますと幸いです。