Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- /*
- Ratkaisun idea: lähdetään rakentamaan uutta merkkijonoa
- merkki kerrallaan. Seuraava huomio on oleellinen: jos jotain
- merkkiä on jäljellä 1 enemmän kuin kaikkia muita merkkejä
- yhteensä, niin joudumme lisäämään sen. Esimerkiksi tilanteessa
- jossa jäljellä olevat kirjaimemme olisivat c,c,c,a,b joudumme
- käyttämään merkit a ja b erottamaan merkkejä c toisistaan.
- Sijoittaisimme ne siis merkkijonoon seuraavasti: cacbc.
- Algoritmi toimii seuraavasti: pidetään aina muistissa edellisessä
- indeksissä olevaa kirjainta. Sen lisäksi tarkistamme aina
- onko jotain kirjainta jäljellä yksi kappale enemmän kuin muita
- kirjaimia yhteensä. Jos tällainen kirjain löytyy, sijoitamme sen
- rakennettavan merkkijonon perälle. Muutoin sijoitamme merkkijonoon
- pienimmän kirjaimen, jota on jäljellä ja joka ei esiinny edellsisessä
- indeksissä.
- */
- public class Main {
- public static String jarjestaMerkit(String mjono) {
- int n=mjono.length();
- int[] merkkien_esiintyvyys=new int[256];
- for(int i=0; i<n; i++)
- merkkien_esiintyvyys[mjono.charAt(i)]++;
- StringBuilder vastaus=new StringBuilder();
- int jaljella=n;
- int kirjain_vasemmalla=-1;
- while(jaljella!=0){
- boolean pakko=false;
- for(int i='A'; i<='Z'; i++){
- if(merkkien_esiintyvyys[i]*2==jaljella+1){
- merkkien_esiintyvyys[i]--;
- pakko=true;
- vastaus.append((char)(i));
- jaljella--;
- kirjain_vasemmalla=i;
- break;
- }
- }
- if(pakko)
- continue;
- for(int i='A'; i<='Z'; i++){
- if(merkkien_esiintyvyys[i]!=0&&i!=kirjain_vasemmalla){
- merkkien_esiintyvyys[i]--;
- vastaus.append((char)(i));
- jaljella--;
- kirjain_vasemmalla=i;
- break;
- }
- }
- }
- return vastaus.toString();
- }
- public static void main(String[] args) {
- System.out.println(jarjestaMerkit("BAAACCC"));
- System.out.println(jarjestaMerkit("CBAED"));
- System.out.println(jarjestaMerkit("AXAXA"));
- System.out.println(jarjestaMerkit("CBAXXXX"));
- }
- }
Add Comment
Please, Sign In to add comment