Tym razem probuje napisac algorytm do tego zadania: http://pl.spoj.pl/problems/NAMES/
Probowalem zoptymalizowac na kazdy sposob jaki mi tylko przyszedl do glowy, juz na kilkanascie roznych sposobow.
Najszybsze rozwiazanie jakie udalo mi sie napisac bylo takie:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;
class Main {
private static class Sort implements Comparator<String> {
public int compare(String i1, String i2) {
String[] t1=i1.split(" ");
String[] t2=i2.split(" ");
int i=Integer.parseInt(t1[1]);
int j=Integer.parseInt(t2[1]);
int k=j-i;
if(k!=0) return k;
else return t1[0].compareTo(t1[0]);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String slowo=" ";
Map<String, Integer> licznik = new TreeMap<String, Integer>();
while(slowo!=null) {
slowo=br.readLine();
if(slowo!=null && slowo.length()>1) {
slowo=slowo.split(" ")[2].toUpperCase();
if(licznik.get(slowo)!=null) {
int ilosc=licznik.get(slowo)+1;
licznik.remove(slowo);
licznik.put(slowo, ilosc);
}
else licznik.put(slowo, 1);
}
}
Collection imiona=licznik.keySet();
Collection ilosci=licznik.values();
Iterator it=imiona.iterator();
Iterator it2=ilosci.iterator();
Collection<String> lista=new ArrayList<String>();
for(int i=0; i<imiona.size(); i++) {
lista.add(it.next()+" "+it2.next());
}
Collections.sort((ArrayList<String>) lista,new Sort());
for(String s: lista) System.out.println(s);
}
}
Jednak jest zbyt wolne. Jesli bym nie musial sortowac na koniec wg. ilosc wystapien (czyli wg. wartosci kluczy) to bym sie w czasie miescil, ale niestety jakos to posortowac musze, jednak po takim sortowaniu przekraczam limit czasu. Moze wiec da sie jakos szybciej to posortowac?
Probowalem tez inaczej.
Zrobilem rowniez cos takiego jak ponizej ale wciaz za wolne:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collection;
import java.util.Iterator;
import java.util.TreeSet;
class Main {
private static class Imie<Typ1, Typ2> implements Comparable<Imie<Typ1,Typ2>> {
protected Typ1 nazwa;
protected Typ2 ilosc;
public Imie(String nazwa, int ilosc) {
this.nazwa=(Typ1) nazwa;
this.ilosc=(Typ2) String.valueOf(ilosc);
}
public void zwieksz() {
int il=Integer.parseInt((String) ilosc);
il++;
ilosc=(Typ2) String.valueOf(il);
}
public int compareTo(Imie<Typ1, Typ2> o) {
int il=Integer.parseInt((String) ilosc);
int il2=Integer.parseInt((String) o.ilosc);
return il2-il!=0?il2-il:((String) nazwa).compareTo((String) o.nazwa);
}
public boolean equals(Object o) {
return ((String) nazwa).equals((String) ((Imie<String,Integer>) o).nazwa);
}
public int getIlosc() {
return Integer.parseInt((String) ilosc);
}
public String toString() {
return (String) nazwa+" "+getIlosc();
}
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String slowo=" ";
Collection<Imie<String,Integer>> licznik=new TreeSet<Imie<String,Integer>>();
while(slowo!=null) {
slowo=br.readLine();
if(slowo!=null && slowo.length()>1) {
slowo=slowo.split(" ")[2].toUpperCase();
Imie<String,Integer> nowe=new Imie<String,Integer>(slowo,1);
Iterator<Imie<String,Integer>> it =licznik.iterator();
boolean dalej=true;
while(it.hasNext() && dalej) {
Imie<String,Integer> imie=it.next();
if(imie.equals(nowe)) {
imie.zwieksz();
licznik.add(imie);
dalej=false;
}
}
if(dalej) licznik.add(nowe);
}
}
for(Imie<String,Integer> s: licznik) System.out.println(s);
}
}
Moj ostatni pomysl byl taki:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collection;
import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;
class Imie implements Comparable<Imie> {
String imie;
int n;
public Imie(String imie, int ilosc) {
this.imie=imie;
n=ilosc;
}
public Imie(Imie im) {
imie=im.imie;
n=im.n;
}
void zwieksz() {
n++;
}
public int compareTo(Imie imtor) {
return imtor.n-n==0?imie.compareToIgnoreCase(imtor.imie):imtor.n-n;
}
public boolean equals(Object o) {
return ((Imie) o).imie.equalsIgnoreCase(imie);
}
public String toString() {
return imie.toUpperCase()+" "+n;
}
}
class Main {
public static void main(String[] args) {
Scanner s = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
Collection<Imie> lista=new TreeSet<Imie>();
while(s.hasNext()) {
s.next();
s.next();
Imie nowy=new Imie(s.next(),1);
Iterator<Imie> it=lista.iterator();
boolean dalej=true;
while(it.hasNext() && dalej) {
Imie next=it.next();
if(next.equals(nowy)) {
nowy=new Imie(next);
nowy.zwieksz();
dalej=false;
it.remove();
}
else if(next.imie.compareTo(nowy.imie)>0) dalej=false;
}
lista.add(nowy);
}
for(Imie im: lista) System.out.println(im);
}
}
Innym pomyslem bylo wykorzystanie interfejsu Map w sposob nastepujacy (jednak wydaje mi sie on juz zbyt przekombinowany i wolny):
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeSet;
class Imie implements Comparable<Imie> {
Map<String,Integer> im;
public Imie(String imie, int ilosc) {
im=new HashMap<String,Integer>();
im.put(imie, ilosc);
}
public Imie(Imie imie) {
im=imie.im;
}
void zwieksz() {
int n=im.values().iterator().next();
String i=im.keySet().iterator().next();
im.clear();
im.put(i,n+1);
}
public int compareTo(Imie imie) {
int i=im.values().iterator().next();
int i2=imie.im.values().iterator().next();
return i2-i==0?im.keySet().iterator().next().compareTo(imie.im.keySet().iterator().next()):i2-i;
}
public boolean equals(Object o) {
return ((Imie) o).im.keySet().iterator().next().equalsIgnoreCase(im.keySet().iterator().next());
}
public int porownanie(Imie imie) {
return im.keySet().iterator().next().compareTo(imie.im.keySet().iterator().next());
}
public String toString() {
return im.keySet().iterator().next().toUpperCase()+" "+im.values().iterator().next();
}
}
class Main {
public static void main(String[] args) {
Scanner s = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
Collection<Imie> lista=new TreeSet<Imie>();
while(s.hasNext()) {
s.next();
s.next();
Imie nowy=new Imie(s.next(),1);
Iterator<Imie> it=lista.iterator();
boolean dalej=true;
while(it.hasNext() && dalej) {
Imie next=it.next();
if(next.equals(nowy)) {
nowy=new Imie(next);
nowy.zwieksz();
dalej=false;
it.remove();
}
else if(next.porownanie(nowy)>0) dalej=false;
}
lista.add(nowy);
}
for(Imie im: lista) System.out.println(im);
}
}