はじめに
スキルチェック過去問題集(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
入力例15 3 1 2 3 2 1
出力例11 2
入力例210 2 6 2 0 7 1 3 5 3 2 6
出力例25 1
詳細は**こちら**から問題を確認してみてください!
解き方の流れ
1.大まかな流れを考える
普段はコメントアウトで大まかな流れを書いてから、コードを書いています。
今回はわかりやすいように図で描いてみました!
2.コードを書いてみる
大まかな流れを考えたらコードを書いてみます。
各工程に沿ってコードを書いていきます。スコープが長くなりそうなところはメソッドに分けるようにしています。
①入力1
// 入力
Scanner sc = new Scanner(System.in);
// アクセスログが残っていた日数n
int n = sc.nextInt();
// キャンペーンを行った日数k
int k = sc.nextInt();
②入力2
メソッドに分けます。
まずは配列の初期化、メソッドの呼び出しを記述します。↓
// n日間の訪問者数配列
int[] visitorCount = new int[n];
// 訪問者の数を入力(n日分)
visitorCount = inputVisitor(n, visitorCount, sc);
次にメソッドの中身を書いていきます。↓
/**
* 訪問者の数を入力するメソッド(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日間の訪問者合計値の配列を作る
メソッドに分けます。
まずは配列の初期化、メソッドの呼び出しを記述します。↓
// k日間分の訪問者合計数の配列[n - k + 1]
int[] visitorSumCount = new int[n - k + 1];
// visitorSumCountを算出する
visitorSumCount = visitorSum(visitorCount, n, k, visitorSumCount);
次にメソッドの中身を書いていきます。↓
/**
* 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値を求める
メソッドに分けます。
まずは変数の初期化、メソッドの呼び出しを記述します。↓
// visitorSumCountの中でMaxの値
int visitorSumMax = 0;
// visitorSumMaxを求める
visitorSumMax = sortVisitorSumMax(visitorSumCount, visitorSumMax);
次にメソッドの中身を書いていきます。↓
/**
* 訪問者合計値の中で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値になるインデックス値をリストに入れる
// visitorSumMaxになるindex値を入れたリスト
List<Integer> visitorSumMaxStartDay = new ArrayList<>();
// visitorSumMaxStartDayを求める
visitorSumMaxStartDay = visitorSumMaxStartDaySort(visitorSumCount, visitorSumMax, visitorSumMaxStartDay);
次にメソッドの中身を書いていきます。↓
/**
* 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の値を出力します。
// 候補日の数を出力
System.out.print(visitorSumMaxStartDay.size() + " ");
// 候補日の最初の日を出力
System.out.print(visitorSumMaxStartDay.get(0) + 1);
解答コード
最後に解答コードを載せます!
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;
}
}
おわりに
ここまで見て頂き、ありがとうございました!
何かご意見や改善箇所などありましたら、コメント頂けますと幸いです。