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/Housy5 Apr 17 '24
How about forgetting all them stacks and just use a int as a cursor and StringBuffer to insert and delete chars in what ever index the cursor is current is at and increment or decrement the cursor when you need to go left or right.