r/learnjava • • 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

12 comments sorted by

View all comments

1

u/-doublex- Apr 17 '24

Is it normal that the input comes from stdin?

1

u/pyeri Apr 17 '24

Yep. that's how it works with other languages and even with Java with earlier problems I've solved.

The issue here is of performances for test cases with larger input.

1

u/-doublex- Apr 17 '24

Ah ok so you confirm you get points for small inputs. You should still pay attention to this comment in their knowledge base:

Scanner sc = new Scanner(System.in); /* Note that scanner can be very slow on large inputs. Consider using a buffered reader such as the KattIO library if the problem has large inputs*/

Just to make sure it has nothing to do with reading the input.

1

u/pyeri Apr 17 '24

Thanks for bringing that to notice! I will look into this.

Small inputs work fine on my local machine.

1

u/-doublex- Apr 17 '24

Yeah, your code seems to run in O(n) so I can't see any issues there. Maybe just too much memory used by keeping two stacks.