I'm doing this problem:
After getting her PhD, Christie has become a celebrity at her university, and her Facebook profile is full of friend requests. Being the nice girl she is, Christie has accepted all the requests.
Now Kuldeep is jealous of all the attention she is getting from other guys, so he asks her to delete some of the guys from her friend list.
To avoid a 'scene', Christie decides to remove some friends from her friend list, since she knows the popularity of each of the friend she has, she uses the following algorithm to delete a friend.
Algorithm Delete(Friend): DeleteFriend=false for i = 1 to Friend.length-1 if (Friend[i].popularity < Friend[i+1].popularity) delete i th friend DeleteFriend=true break if(DeleteFriend == false) delete the last friendInput: First line contains T number of test cases. First line of each test case contains N, the number of friends Christie currently has and K ,the number of friends Christie decides to delete. Next lines contains popularity of her friends separated by space.
Output: For each test case print N-K numbers which represent popularity of Christie friend's after deleting K friends.
Constraints:
1 <= T <= 1000 1 <= N <= 100000 0 <= K < N 0 <= popularity_of_friend <= 100NOTE: Order of friends after deleting exactly K friends should be maintained as given in input.
Sample Input
3 3 1 3 100 1 5 2 19 12 3 4 17 5 3 23 45 11 77 18Sample Output
100 1 19 12 17 77 18Time Limit 1 sec(s) (Time limit is for each input file.)
Memory Limit 256 MB
Source Limit 1024 KB
Initially I would read and add the numbers to the list, then follow that algorithm. I figured doing what that algorithm does except as I add it in would be much faster (which it was):
import java.util.*;
class TestClass {
public static void main(String args[] ) throws Exception {
Scanner scanner = null;
try{
scanner = new Scanner(System.in);
}catch(Exception e){
return;
}
int T = Integer.parseInt(scanner.next());
//remove as i add to list
for(int i = 0; i < T; i++){
int friendsStart = Integer.parseInt(scanner.next());
int friendsDelete = Integer.parseInt(scanner.next());
ArrayList<Integer> inputList = new ArrayList<Integer>();
int currentPos = 0;
for(int j = 0; j < friendsStart ; j++){
p.add(Integer.parseInt(scanner.next()));
if(fD > 0 && currentPos > 0 && inputList.get(currentPos) > inputList.get(currentPos-1)){
inputList.remove(currentPos-1);
friendsDelete--;
currentPos--;
}else{
currentPos++;
}
}
//remove remainder required to remove
while(friendsDelete > 0 && c < inputList.size()){
if(currentPos > 0 && inputList.get(currentPos) > inputList.get(currentPos -1)){
inputList.remove(currentPos-1);
friendsDelete--;
currentPos--;
}else{
currentPos++;
}
}
//print
for(int j = 0; j < inputList.size(); j++){
System.out.print(inputList.get(j) + " ");
}
System.out.println();
}
}
}
However, when I submit, it does some bigger test cases (not sure what the cases are), but it ends up being too slow. I wanted some hints as to how I can make this faster than it already is. I don't want a direct answer.
new ArrayList<Integer>(friendsStart)to avoid copying memory every time it has to double the capacity to make room for more elements. Also, ispthe old name forinputList? \$\endgroup\$