This code is from a competition, it works just fine if I use the built-in Scanner class to read data. But here, in this original solution, they defined a custom class MyScanner to read data? Why is that? Does it has anything to do with the execution time or is there some other purpose? Any reasonable explanation or reference to related concept would be appreciated, thanks in advance.
class Main {
final static int[] coins = {50, 25, 10, 5, 1};
static int[][] memo;
public static void main(String[] args) throws IOException{
MyScanner sc = new MyScanner();
Integer num = 7489 + 1;
memo = new int[num+1][coins.length];
for (int i = 0; i < num+1; i++) {
Arrays.fill(memo[i], -1);
}
while ((num = sc.nextInt()) != null) {
int r = change(num, 0);
System.out.println(r);
}
}
private static int change(int num, int cInd) {
if (num < 0){
return 0;
} else if (num == 0 || cInd == coins.length-1){
return 1;
} else if(memo[num][cInd] != -1) {
return memo[num][cInd];
}else {
int result = change(num, cInd+1) + change(num-coins[cInd], cInd);
return memo[num][cInd] = result;
}
}
static class MyScanner {
BufferedReader br;
StringTokenizer st;
public MyScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
public String next() throws IOException {
if (st == null || !st.hasMoreTokens()) {
String line = br.readLine();
if (line == null){
return null;
}
st = new StringTokenizer(line);
}
return st.nextToken();
}
public Integer nextInt() throws IOException {
String next = next();
if (next != null) {
return Integer.parseInt(next);
} else {
return null;
}
}
}
}
In programming competitions, one of the competition criteria can be how fast the competitor's code is able to process some text-based input file.
You will typically see this kind of thing (the MyScanner
class) used because the developer thinks that gives him or her an "edge" in performance over using the standard classes. People who are "into" competitive programming will develop their own personal toolkits ... to improve their edge.
It is not clear whether this class will really perform better in general, or whether the contribution to the overall performance will be significant. One would need to:
But in one sense, it doesn't matter. What really counts is that the person who uses this kind of code believes it is better. Either way, it does what they think is necessary. The ends justifies the means.
On the other hand, if you were to do this kind of thing in production code, you would probably be doing your project / employer a disservice:
You should only resort to this kind of thing if your profiling of your application shows that scanning is a significant performance bottleneck.
Even then, this kind of thing is most likely wrong:
if (next != null) {
return Integer.parseInt(next);
} else {
return null;
}
since it is liable to be a source of unexpected NPEs.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With