このあたりの話ではないでしょうか。
Like!
ABC279 C問題のボトルネック部分がどこにあるのかを知りたい
解決したいこと
AtCoder ABC279のC問題での私の解答が実行時間制限オーバーしてしまう原因がどこにあるか知りたいです。公式解説と似たような感じで解きました。
以下のような解答をしました。
Main.java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int H = sc.nextInt();
int W = sc.nextInt();
String s[] = new String[H];
String t[] = new String[H];
for(int i = 0; i < H; i++) s[i] = sc.next();
for(int i = 0; i < H; i++) t[i] = sc.next();
//ここまで入力
ArrayList<String> list1 = new ArrayList<>();
ArrayList<String> list2 = new ArrayList<>();
for(int i = 0; i < W; i++){
String n = "";
String n2 = "";
for(int j = 0; j < H; j++){
n += s[j].charAt(i);
n2 += t[j].charAt(i);
}
list1.add(n);
list2.add(n2);
}
Collections.sort(list1);
Collections.sort(list2);
if(list1.equals(list2)) System.out.println("Yes");
else System.out.println("No");
}
}
公式解説は下記に載せておきます。
自分で試したこと
はじめlist1とlist2が同じであるかどうかの判断はlist1とlist2の文字列を初めから順番に一つずつ取り出し比較していました。
equalsメソッドを使うことに変更し、TLEになるテストケースを1つだけ減らすことができました。
for(int i = 0; i < list1.size(); i++){
if(!list1.get(i).equals(list2.get(i))) {
sum += 1;
break;
}
}
if(0 < sum) System.out.println("No");
else System.out.println("Yes");
0
2Answer
1
Comments
@kanenist
Questionerありがとうございます、勉強になりました！
@actorbug さんの回答通りです。
StringをStringBufferに変更するだけで、ACしました。
ABC279-C
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int H = sc.nextInt();
int W = sc.nextInt();
String s[] = new String[H];
String t[] = new String[H];
for(int i = 0; i < H; i++) s[i] = sc.next();
for(int i = 0; i < H; i++) t[i] = sc.next();
//ここまで入力
ArrayList<String> list1 = new ArrayList<>();
ArrayList<String> list2 = new ArrayList<>();
for(int i = 0; i < W; i++){
StringBuffer n = new StringBuffer();
StringBuffer n2 = new StringBuffer();
for(int j = 0; j < H; j++){
n.append(s[j].charAt(i));
n2.append(t[j].charAt(i));
}
list1.add(n.toString());
list2.add(n2.toString());
}
Collections.sort(list1);
Collections.sort(list2);
if(list1.equals(list2)) System.out.println("Yes");
else System.out.println("No");
}
}
Like!
Comments
@kanenist
Questionerソースコードも載せて下さり理解が進みます！
StringBufferについて自分なりに勉強していこうと思います。ありがとうございます！