r/learnjava • u/pyeri • Apr 17 '24
Implementing efficient Stack data structure in Java
Having already solved the Keystrokes problem on Open Kattis using Python3, I'm now trying to re-implement the same algorithm in Java. I've come up with below class which compiles and runs fine but runs into the time-out error when I submit for evaluation. What can I do to make it more efficient?
import java.util.*;
class lyklagangriti {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
Stack<Character> l = new Stack<>();
Stack<Character> r = new Stack<>();
for(int i=0;i<s.length();i++) {
char c = s.charAt(i);
char item;
switch(c) {
case 'L':
item = l.pop();
r.push(item);
break;
case 'R':
item =r.pop();
l.push(item);
break;
case 'B':
l.pop();
break;
default:
l.push(c);
}
}
for(char c : l) {
System.out.print(c);
}
while(r.size() > 0) {
char c = r.pop();
System.out.print(c);
}
System.out.println("");
}
}Edit
Special thanks to /u/Cengo789 for suggesting ArrayDeque instead of Stack, and to /u/-doublex- for suggesting BufferedReader instead of Scanner for reading the input. After implementing these ideas, the program passes the test in only 0.21 seconds!
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
class lyklagangriti {
public static void main(String[] args) throws IOException {
//Scanner sc = new Scanner(System.in);
BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
String s = bi.readLine();
//String s = sc.nextLine();
Deque<Character> l = new ArrayDeque<Character>();
Deque<Character> r = new ArrayDeque<Character>();
for(int i=0;i<s.length();i++) {
char c = s.charAt(i);
char item;
switch(c) {
case 'L':
item = l.pollLast();
r.addFirst(item);
break;
case 'R':
item =r.pollFirst();
l.addLast(item);
break;
case 'B':
l.pollLast();
break;
default:
l.addLast(c);
}
}
StringBuilder sb = new StringBuilder(l.size() + r.size());
for(char c : l) {
sb.append(c);
}
for(char c : r) {
sb.append(c);
}
System.out.println(sb);
}
}
0
Upvotes
1
u/-doublex- Apr 17 '24
Is it normal that the input comes from stdin?