キャンペーンしてたので、Java独学の自分が思考整理の為に記事を書きながら問題を解いてみました
挑戦した問題はランクSの「文字列収集」です。
問題文のコピー
あなたは文字列の愛好家で、文字列を収集することにとても熱心です。
文字列は市場で高値で取引されています。今、市場には N 個の文字列が出まわっており、文字列 S_i (1 ≦ i ≦ N) の価格は P_i です。 あなたは数ある文字列の中でも、とくに先頭がある特定の文字列で始まる文字列に興味があり、そのような文字列をすべて買い占めたいです。例え、同じ文字列が複数売っていたとしてもそのすべてを買います。
そこで、市場に出回っている N 個の文字列 S_i とそれぞれの価格 P_i (i ≦ i ≦ N)、また、M 個のクエリ文字列 Q_i (1 ≦ i ≦ M) が与えられるので、それぞれのクエリ Q_i に対し、市場に出回っている文字列の中で先頭が Q_i で始まる文字列すべてを買い占めるのに必要な金額を出力するプログラムを作成してください。
前提情報
- Javaにおける標準入力の方法は
Scannerクラスを用いる - 空白・改行はデフォルトの区切り文字
-
next()メソッドは次の区切り文字が出るまで文字列として取得 -
nextInt()メソッドは次の区切り文字が出るまで、数値(int型)として取得
思考順序
今回の問題を解く為に行った順序です。
- 問題を解くロジックを考える
- 入力の取得方法を考える
- 得られた入力をロジックにあわせる
- 最適化1（要らない変数やループの削除など）
- 最適化2（バグやエラーが無くなるまで何度も行う）
実際の手順
1．問題を解くロジックを考える
- 今回は
欲しい文字列から始まる文字列を探して、その価格を合計するので、
StringクラスのstartWith()メソッドを利用する - 出回っている文字列とその価格をセットでマップなどに格納すると、コードが書きやすそう
- あとは探したい文字列をリストに入れてループさせ、そのループの中で 出回っている文字列でループをして価格を合計 すれば求めた結果が得られそう
具体的なロジックは以下のコードになりそうです。
List 価格のリスト = new LinkedList<>();
for(探したい文字列のリストでループ){
int price = 0;
for(出回ってる文字列でループ){}
if(探したい文字列から始まる?){
price += 文字の価格;
}
}
価格のリスト.add(price);
}
2．入力の取得方法を考える
次に標準入力から得られる入力を取得する方法を考えます。
まず大まかなコードの流れを考えます。
Scanner sc = new Scanner(System.in);
int 出回っている文字列の個数 = sc.取得();
int 探したい文字列の個数 = sc.取得();
Map 文字列と価格のマップ = new HashMap<>();
for(0から「出回っている文字列の個数」までループ){
String 文字 = sc.取得();
int 価格 = sc.取得();
文字列と価格のマップ.put(文字, 価格);
}
List 探したい文字列のリスト = new LinkedList<>();
for(0から「探したい文字列の個数」までループ){
String 文字 = sc.取得();
文字列のリスト.add(文字);
}
これを元に具体的なコードを考えます。
まず一行目で出回っている文字列の個数と探したい文字列の個数が空白で区切られて入力されます。
なので数値専用のnextInt()を2回使ってそれぞれをローカル変数のstringNumとqueryNumに格納します。
Scanner sc = new Scanner(System.in);
int stringNum = sc.nextInt();
int queryNum = sc.nextInt();
そして得られた数値を使ってforループで出回っている文字列（と価格）と探したい文字列を取得します。
文字列と価格は対応しているので、Mapクラスを使って対応させて保持します。
Map<String, Integer> stringMap = new HashMap<>()
for(int i = 0; i < stringNum; i++){
String str = sc.next();
int price = sc.nextInt();
stringMap.put(str, price);
}
探したい文字列も先ほどと同様に取得しますが、こちらは価格がないのでListクラスで保持します。
List<String> searchList = new LinkedList<>();
for(int i = 0; i < queryNum; i++){
String str = sc.next();
searchList.add(str);
}
纏めたコードがこちら
public static void main(String[] args){
// 標準入力から各情報を取得
Scanner sc = new Scanner(System.in);
int stringNum = sc.nextInt();
int queryNum = sc.nextInt();
Map<String, Integer> stringMap = new HashMap<>()
for(int i = 0; i < stringNum; i++){
String str = sc.next();
int price = sc.nextInt();
stringMap.put(str, price);
}
List<String> searchList = new LinkedList<>();
for(int i = 0; i < queryNum; i++){
String str = sc.next();
searchList.add(str);
}
}
3．得られた入力をロジックにあわせる
今回はそこまで改変しなくても使えそうですが、ロジックは入力方法を考慮せずに作ったので、大抵の場合は入力を取得する時の方法（mapかListかなど）は改変した方が良いです。
// 入力取得のコードは省略
Map<String, Integer> stringMap = new ArrayMap<>()
List<String> searchList = new LinkedList<>();
// ロジック↓
List<Integer> priceList = new LinkedList<>();
for(int i = 0; i < searchList.size(); i++){
int price = 0;
for(string s : stringMap.keySet()){
if(s.startsWith(str)){
price += stringMap.get(s);
}
}
priceList.add(price);
}
for(int i = 0; i < priceList.size(); i++){
System.out.println(priceList.get(i));
}
4．最適化1
現状のコードにはfor文の中にfor文があったり、結果を表示するのにforループを使ったりして見づらくなっています。
なのでfor-each文（拡張for文）やメソッド参照などを用いてコードの最適化をします。
長いので折りたたんでいます。
最適化1差分
public class Main {
public static void main(String[] args){
// 標準入力から各情報を取得
Scanner sc = new Scanner(System.in);
int stringNum = sc.nextInt();
int queryNum = sc.nextInt();
Map<String, Integer> stringMap = new HashMap<>()
for(int i = 0; i < stringNum; i++){
String str = sc.next();
int price = sc.nextInt();
stringMap.put(str, price);
}
List<String> searchList = new LinkedList<>();
for(int i = 0; i < queryNum; i++){
String str = sc.next();
searchList.add(str);
}
// ロジック↓
List<Integer> priceList = new LinkedList<>();
- for(int i = 0; i < searchList.size(); i++){
+ for(String str : searchList){
int price = 0;
for(string s : stringMap.keySet()){
- if(s.startsWith(searchList.get(i))){
+ if(s.startsWith(str)){
price += stringMap.get(s);
}
}
}
priceList.add(price);
}
- for(int i = 0; i < priceList.size(); i++){
- System.out.println(priceList.get(i));
- }
+ priceList.forEach(System.out::println);
}
}
またStreamを使えばより見やすくなる場合もあります。
今回はforループ内でそれほど大きな処理をしないためそのままでも良さそうです。
Streamを使用したコードの例
// 方法1
for(String str : searchList){
int price = 0;
for(String s : stringMap.keySet()){
if(s.startsWith(str)){
price += stringMap.get(s);
}
}
priceList.add(price);
}
// 方法2
searchList.forEach(str -> {
int price = stringMap.entrySet().stream()
.filter(e -> e.getKey().startsWith(str))
.mapToInt(Map.Entry::getValue)
.sum();
priceList.add(price);
});
5．最適化2
「実際に実行してみて、バグやエラーを修正し、再び実行」をバグやエラーがなくなるまで繰り返します。
ここで誤字脱字なども修正します。
自分もよく誤字脱字をしてコンパイラに怒られてます
IntegerをIntegetと間違えたり、存在しないArrayMapを書いてしまったりしました
実際に最適化1をしたコードを実行してみた結果、間違いがありました。
理由は「出回っている文字列」に同じ文字があったため、変数stringMapに格納(put)する際に同じ文字が上書きされていました。
Mapクラスを継承するクラスはいずれも同じキーを格納する事ができないので、今回はListクラスのオブジェクトを使用し、また新たに以下の様なMojiretuクラスを創ります。
Mojiretuクラスにはメンバ変数として文字列と価格を保持します。
class Mojiretu {
public final String mojiretu;
public final int price;
public Mojiretu(String s, int p){
mojiretu = s;
price = p;
}
}
修正差分はこちら
public class Main {
public static void main(String[] args){
// 標準入力から各情報を取得
Scanner sc = new Scanner(System.in);
int stringNum = sc.nextInt();
int queryNum = sc.nextInt();
- Map<String, Integer> stringMap = new HashMap<>()
+ List<Mojiretu> stringList = new LinkedList<>();
for(int i = 0; i < stringNum; i++){
String str = sc.next();
int price = sc.nextInt();
- stringMap.put(str, price);
+ stringList.add(new Mojiretu(str, price));
}
List<String> searchList = new LinkedList<>();
for(int i = 0; i < queryNum; i++){
String str = sc.next();
searchList.add(str);
}
// ロジック↓
List<Integer> priceList = new LinkedList<>();
for(String str : searchList){
int price = 0;
- for(String s : stringMap.keySet()){
- if(s.startsWith(str)){
- price += stringMap.get(s);
+ for(Mojiretu m : stringList){
+ if(m.mojiretu.startsWith(str)){
+ price += m.price;
}
}
priceList.add(price);
}
priceList.forEach(System.out::println);
}
}
+ class Mojiretu {
+ public final String mojiretu;
+ public final int price;
+ public Mojiretu(String s, int p){
+ mojiretu = s;
+ price = p;
+ }
+ }
最終的に完成したコードがこちら
public class Main {
public static void main(String[] args){
// 標準入力から各情報を取得
Scanner sc = new Scanner(System.in);
int stringNum = sc.nextInt();
int queryNum = sc.nextInt();
List<Mojiretu> stringList = new LinkedList<>();
for(int i = 0; i < stringNum; i++){
String str = sc.next();
int price = sc.nextInt();
stringList.add(new Mojiretu(str, price));
}
List<String> searchList = new LinkedList<>();
for(int i = 0; i < queryNum; i++){
String str = sc.next();
searchList.add(str);
}
// ロジック↓
List<Integer> priceList = new LinkedList<>();
for(String str : searchList){
int price = 0;
for(Mojiretu m : stringList){
if(m.mojiretu.startsWith(str)){
price += m.price;
}
}
priceList.add(price);
}
priceList.forEach(System.out::println);
}
}
class Mojiretu {
public final String mojiretu;
public final int price;
public Mojiretu(String s, int p){
mojiretu = s;
price = p;
}
}
結果
テストデータでエラー等が無くなったので提出したところ、無事合格できました。
実行時間
平均0.20秒
最短0.11秒（テスト1、2）
最長0.27秒（テスト9）
でした。
振り返り
今回の反省点は最適化1の前に一度テストを実行すべきでした。
コードの量よりも正しく実行できるかが重要なので、主にコード量の減少を目的とした最適化は、きちんと実行できるかを確かめた後でするべきでした。
今回は最適化1の前後で発生するエラーが変わらないため支障はありませんでしたが、今後は最適化の前にまず一度実行しようと思います。てかします。
また今回はMojiretuクラスを新たに作って出回っている文字列1つにつき1つのオブジェクトを生成しましたが、オブジェクト生成には大きなコストが掛かるので実行時間や使用メモリが限られた環境では使用できない方法かもしれません。
今回初めて思考を記事として書いて説明しながら問題を解いてみましたが、時間はもちろんいつも以上に掛かりましたが、自分の考えている事をより理解できたとともに、思考に悪いくせがあるのもみつかりました。
記録に残るので思い返しやすく、初心者ほどした方が良いと思いました。
また最近
JavaScriptばかり書いていたので基本的なところでいくつか忘れていた部分もありましたが、書いているうちに思い出して中盤からはスラスラ書けたのはよかったです^^
あとはIDEのありがたさもとても分かりました