АПС - Статистика

/*
Max likes football very much. In order to check the popuplarity of the game, he decided to talk to random people and ask them about their favourite game and note it down in a list.

Given a list of name of people and their favourite sport, help Max in finding the sport liked by most of the people, and also how many people like football.

He could have met same people more than once, he will only count response of his first meet with any person.

Note : Name of person as well as sport is a single string in lowercase. Length of name of people as well as sport is less than 11.

Input :: First line will contain no of entries in the list. i.e. N Next N lines will contain two strings, person's name and sports he like.

Output :: In first ine, name of sport liked by most no of people (In case of more than one games is liked by highest no of people, output the first one in lexicographical order). In second line, no of people having football as their favourite game.

Constraints: 1<=N<=100000 1<=Name of person<=10 1<=Name of sport<=10


SAMPLE INPUT

5
Filip Odbojka
Frose Kosarka
Pedza Odbojka
Vlado Kosarka
Davor Fudbal


SAMPLE OUTPUT
NAJPOPULAREN SPORT: odbojka
FUDBAL SAKAAT: 1
*/

import java.util.*;
import java.io.*;

class SLLNode<E> {
    protected E element;
    protected SLLNode<E> succ;

    public SLLNode(E elem, SLLNode<E> succ) {
        this.element = elem;
        this.succ = succ;
    }

    @Override
    public String toString() {
        return element.toString();
    }
}

class SLL<E> {

    private SLLNode<E> first;

    public SLL() {
        // Construct an empty SLL
        this.first = null;
    }

    public void deleteList() {
        first = null;
    }

    public int length() {
        int ret;
        if (first != null) {
            SLLNode<E> tmp = first;
            ret = 1;
            while (tmp.succ != null) {
                tmp = tmp.succ;
                ret++;
            }
            return ret;
        } else {
            return 0;
        }

    }

    @Override
    public String toString() {
        String ret = new String();
        if (first != null) {
            SLLNode<E> tmp = first;
            ret += tmp + " ";
            while (tmp.succ != null) {
                tmp = tmp.succ;
                ret += tmp + " ";
            }
        } else {
            ret = "Prazna lista!!!";
        }
        return ret;
    }

    public void insertFirst(E o) {
        SLLNode<E> ins = new SLLNode<E>(o, first);
        first = ins;
    }

    public void insertAfter(E o, SLLNode<E> node) {
        if (node != null) {
            SLLNode<E> ins = new SLLNode<E>(o, node.succ);
            node.succ = ins;
        } else {
            System.out.println("Dadenot jazol e null");
        }
    }

    public void insertBefore(E o, SLLNode<E> before) {

        if (first != null) {
            SLLNode<E> tmp = first;
            if (first == before) {
                this.insertFirst(o);
                return;
            }
            // ako first!=before
            while (tmp.succ != before) {
                tmp = tmp.succ;
            }
            if (tmp.succ == before) {
                SLLNode<E> ins = new SLLNode<E>(o, before);
                tmp.succ = ins;
            } else {
                System.out.println("Elementot ne postoi vo listata");
            }
        } else {
            System.out.println("Listata e prazna");
        }
    }

    public void insertLast(E o) {
        if (first != null) {
            SLLNode<E> tmp = first;
            while (tmp.succ != null) {
                tmp = tmp.succ;
            }
            SLLNode<E> ins = new SLLNode<E>(o, null);
            tmp.succ = ins;
        } else {
            insertFirst(o);
        }
    }

    public E deleteFirst() {
        if (first != null) {
            SLLNode<E> tmp = first;
            first = first.succ;
            return tmp.element;
        } else {
            System.out.println("Listata e prazna");
            return null;
        }
    }

    public E delete(SLLNode<E> node) {
        if (first != null) {
            SLLNode<E> tmp = first;
            if (first == node) {
                return this.deleteFirst();
            }
            while (tmp.succ != node && tmp.succ.succ != null) {
                tmp = tmp.succ;
            }
            if (tmp.succ == node) {
                tmp.succ = tmp.succ.succ;
                return node.element;
            } else {
                System.out.println("Elementot ne postoi vo listata");
                return null;
            }
        } else {
            System.out.println("Listata e prazna");
            return null;
        }

    }

    public SLLNode<E> getFirst() {
        return first;
    }

    public SLLNode<E> find(E o) {
        if (first != null) {
            SLLNode<E> tmp = first;

            while (tmp.element != o && tmp.succ != null) {
                tmp = tmp.succ;
            }
            if (tmp.element == o) {
                return tmp;
            } else {
                System.out.println("Elementot ne postoi vo listata");
            }
        } else {
            System.out.println("Listata e prazna");
        }
        return first;
    }

    public Iterator<E> iterator() {
        // Return an iterator that visits all elements of this list, in left-to-right
        // order.
        return new LRIterator<E>();
    }

    // //////////Inner class ////////////
    private class LRIterator<E> implements Iterator<E> {

        private SLLNode<E> place, curr;

        private LRIterator() {
            place = (SLLNode<E>) first;
            curr = null;
        }

        public boolean hasNext() {
            return (place != null);
        }

        public E next() {
            if (place == null) {
                throw new NoSuchElementException();
            }
            E nextElem = place.element;
            curr = place;
            place = place.succ;
            return nextElem;
        }

        public void remove() {
            // Not implemented
        }
    }

    public void mirror() {
        if (first != null) {
            // m=nextsucc, p=tmp,q=next
            SLLNode<E> tmp = first;
            SLLNode<E> newsucc = null;
            SLLNode<E> next;

            while (tmp != null) {
                next = tmp.succ;
                tmp.succ = newsucc;
                newsucc = tmp;
                tmp = next;
            }
            first = newsucc;
        }

    }

    public void merge(SLL<E> in) {
        if (first != null) {
            SLLNode<E> tmp = first;
            while (tmp.succ != null) {
                tmp = tmp.succ;
            }
            tmp.succ = in.getFirst();
        } else {
            first = in.getFirst();
        }
    }
}

public class SportskaStatistika {

    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(in.readLine());

        HashMap<String, SLL<Covek>> table = new HashMap<String, SLL<Covek>>(2 * n + 1);

        for (int i = 0; i < n; i++) {

            SLL<Covek> lista = null;

            String line = in.readLine();
            String[] niza = line.split(" ");

            Covek c = new Covek(niza[0], niza[1]);

            if (table.containsKey(c.sport)) {
                lista = table.get(c.sport);
                lista.insertLast(c);
                table.put(c.sport, lista);
            } else {
                lista = new SLL<Covek>();
                lista.insertLast(c);
                table.put(c.sport, lista);
            }
        }
        brisiDuplikati(table);
        String najpopularenKluc = najpopularenSport(table);
        System.out.println("NAJPOPULAREN SPORT: " + najpopularenKluc);
        System.out.println("FUDBAL SAKAAT: " + najdiFudbal(table));

    }

    public static int najdiFudbal(HashMap<String, SLL<Covek>> table) {
        SLL<Covek> lista = table.get("fudbal");
        if(lista==null) {
            return 0;
        }
        SLLNode<Covek> dvizi = lista.getFirst();
        int count = 0;

        while (dvizi != null) {
            count++;
            dvizi = dvizi.succ;
        }
        return count;
    }

    public static String najpopularenSport(HashMap<String, SLL<Covek>> table) {
        Set<String> klucovi = table.keySet();
        String[] klucevi = klucovi.toArray(new String[klucovi.size()]);
        int max = 0;
        String maxKey = null;
        for (String s : klucevi) {
            int count = 0;
            SLL<Covek> lista = table.get(s);
            SLLNode<Covek> dvizi = lista.getFirst();
            while (dvizi != null) {
                count++;
                dvizi = dvizi.succ;
            }
            if (count >= max) {
                max = count;
                maxKey = s;
            }

        }
        return maxKey;
    }

    public static HashMap<String, SLL<Covek>> brisiDuplikati(HashMap<String, SLL<Covek>> table) {
        Set<String> klucovi = table.keySet();
        String[] klucevi = klucovi.toArray(new String[klucovi.size()]);

        for (String s : klucevi) {

            SLL<Covek> lista = table.get(s);
            SLLNode<Covek> dvizi = lista.getFirst();

            while (dvizi != null) {
                SLLNode<Covek> dviziNapred = dvizi.succ;

                while (dviziNapred != null) {
                    if (dvizi.element.compareTo(dviziNapred.element) == 1) {
                        lista.delete(dviziNapred);
                    }
                    dviziNapred = dviziNapred.succ;
                }
                dvizi = dvizi.succ;
            }
        }
        return table;
    }

}

class Covek implements Comparable<Covek> {
    protected String ime;
    protected String sport;

    public Covek() {
    }

    public Covek(String ime, String sport) {
        this.ime = ime;
        this.sport = sport.toLowerCase();
    }

    @Override
    public String toString() {
        return ime;
    }

    @Override
    public int compareTo(Covek c) {
        if (ime.equals(c.ime)) {
            return 1;
        }
        return 0;
    }

}