CCO ’99 P2 – Common Words

Canadian Computing Competition: 1999 Stage 2, Day 1, Problem 2

Given a sequence of  words from a newspaper article and an integer , find the  most common word(s).

Input Specification

Input will consist of an integer  followed by  data sets. Each data set begins with a line containing  and , followed by  lines, each containing a word of up to  lowercase letters. There will be no more than  words per data set.

Output Specification

For each input data set, determine the  most common word(s). To be precise, a word  is the  most common if exactly  distinct words occur more frequently than  in the data set. Note that  might be multiply defined (i.e. there is a tie for the  most common word) or  might not exist (i.e. there is no  most common word). For each data set, print a title line indicating  using normal ordinal notation (1st, 2nd, 3rd, 4th, 5th, …) followed by a number of lines giving all the possible values for the  most common word. A blank line should follow the last word for each data set.

Sample Input

Copy

3
7 2
the
brown
the
fox
red
the
red
1 3
the
2 1
the
wash

Sample Output

Copy

2nd most common word(s):
red

3rd most common word(s):

1st most common word(s):
the
wash

Solution

import java.util.*;
import java.io.*;
public class Main {

	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(System.in);
       int cases = in.nextInt();
       for(int o=0; o < cases; o++){
       	int words = in.nextInt(), rank = in.nextInt();
		   System.out.print(rank);
		   if(rank % 100 >10 && rank % 100 < 20 || rank > 1000){
			   System.out.print("th");
		   }else {
		   	switch(rank %10){
				case 1:{
					System.out.print("st");
					break;
				}
				case 2:{
					System.out.print("nd");
					break;
				}
				case 3:{
					System.out.print("rd");
					break;
				}
				default:{
					System.out.print("th");
					break;
				}

			}
		   }
		   System.out.println(" most common word(s):");
		   String a[] = new String[words];
		   for(int i=0; i < a.length; i++){
		   	a[i] = in.next();
		   }
		   ArrayList<String> output = tester(a, rank);
		   if(output.isEmpty()){
			   System.out.println();
			   continue;
		   }else {
		   	for(int i=0; i < output.size(); i++){
				System.out.println(output.get(i));
			}
			   System.out.println();
		   }
	   }
	}
       public static ArrayList<String> tester(String a[], int place){
		ArrayList<String> returner = new ArrayList<String>();
		   Arrays.sort(a);
		   Set<String> ref = new HashSet<String>();
		   for(int i=0; i < a.length; i++){
		   	ref.add(a[i]);
		   }
		   HashMap<String, Integer> results  = new HashMap<String, Integer>();
		   for(String x:ref){
		   	int counter = 0;
		   	for(int i=0; i < a.length; i++){
		   		if(a[i].equals(x)){
		   			counter++;
				}
			}
		   	results.put(x, counter);
		   }
          ArrayList<String> sorter  = new ArrayList<String>();
		   Set<Integer> sorter1  = new HashSet<Integer>();
		   for(String u: ref){
		   	sorter1.add(results.get(u));
		   }
		   ArrayList<Integer> sort   = new ArrayList<Integer>(sorter1);
		   Collections.sort(sort);
		   for(int m=sort.size()-1; m >= 0; m--){
		   	int istrue= sort.get(m);
		   	for(String v: ref){
		   		if(results.get(v) == istrue){
		   			sorter.add(m+" " + String.valueOf(istrue));
				}
			}
		   }
		  if(place>sorter.size()){
		      return returner;
		  }else {
		  	String p[] = sorter.get(place-1).split(" ");
		  	int compare = Integer.parseInt(p[1]);
		  	int rrr = 0;
		  	for(int g=place-1; g >= 0; g--){
		  		String o[] = sorter.get(g).split(" ");
		  		if(Integer.parseInt(o[1])  > compare){
		  			rrr++;
				}
			}
		  	if(rrr == place-1){
		  		for(String s:ref){
		  			if(results.get(s) == compare){
		  				returner.add(s);
					}
				}
			}else {
		  		return returner;
			}
		  }



             return returner;
	   }
}