2
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Last updated at Posted at 2020-08-26

はじめに

スキルチェック過去問題集(Java編)から「日別訪問者数の最大平均区間 (paizaランクB相当)」を解いてみました:blush:
プログラム初心者ですが、アルゴリズムの部分もわかりやすくまとめてみました!
ちなみに筆者は実務未経験の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.大まかな流れを考える

普段はコメントアウトで大まかな流れを書いてから、コードを書いています。
今回はわかりやすいように図で描いてみました!
日別訪問者問題.png

2.コードを書いてみる

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


①入力1

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

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

②入力2

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

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日間の訪問者合計値の配列を作る

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

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値を求める

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

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値になるインデックス値をリストに入れる

image.png

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;
	}

⑥出力

image.png

これで最後です!
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;
	}
}

おわりに

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

2
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?