Leksikografski minimum, potrebna pomoć [Zadatak iz zbirke]

Pitanja i problemi
1

Pozdrav svima,
Imam problem sa zadatkom iz BubbleBee zbirke, pod nazivom "Leksikografski minimum" , pokušavao sam ga rešiti na brojne načine i nijedan od njih nije pogodio sve test primere, već otprilike pola njih. Ako neko zna optimalno rešenje za ovaj zadatak, značilo bi mi kada bi to rešenje napisao ovde i objasnio.

Evo koda:

#include <bits/stdc++.h>

using namespace std;

void print(const string& item)
{
    cout << item << endl;
}

int main()
{
    set<string> sortedItems;
    string k;
    string s;
    string buffer = "";
    getline(cin, k);
    for (long long i = 0; i < k.length(); i++){
        if (k[i] != ' ') buffer += tolower(k[i]);
        if (k[i] == ' ' || i == k.length()-1) {
            sortedItems.insert(buffer);
            buffer = "";
        }
    }
    for(auto it = sortedItems.begin(); it != sortedItems.end(); it++)
    {
        s = *it;
        break;
    }
    cout << s;
    return 0;
}

Hvala unapred!

2

Možda nije dovoljno dobro objašnjeno u zаdatku, ali potrebno je da reč ispišeš isto onako (sa istim velikim/malim slovima kao što je bila na ulazu). Npr. za “KO RaNO RANI DvE SRECE GRABI” tvoj program će ispisati “dve”, a tačno rešenje je “DvE”.

Osvrnuo bih se malo i na tvoj kod. Možda su ti neke stvari ostale zbog testiranja, ali bih napomenuo ovde za svaki slučaj. Npr, za početak ovu for petlju:

   for(auto it = sortedItems.begin(); it != sortedItems.end(); it++)
   {
       s = *it;
       break;
   }

možeš zameniti jednostavnom naredbom:

 s = *sortedItems.begin();

Druga stvar, iako ovde nije netačno, uopšte nije neophodno koristiti strukturu set, dovoljno je da pamtiš samo jedan string koji je trenutno leksikografski najmanji, i da svaku novu reč porediš sa njim, i eventualno ažuriraš taj string ako je nova reč leksikografski manja od njega. Osim što će ti program tako biti brži (jer set svaki put drži sortirano stablo svih podataka što ti ovde nije neophodno), biće ti i lakše da uradiš ovaj konkretan zadatak gde treba ispisati reč onako kako je na ulazu.

1 Like
3

Zdravo Vuče,

Ja imam još jedan komentar, koji nije neophodan za rešavanje zadatka, ali je, nadam se, svejedno korisan:

Podatke učitavaš na previše komplikovan način, koji je uz to previše osetljiv. Na primer, proveri šta se desi kada svom programu daš sledeći ulaz:

a<razmak><razmak>b

Da li možeš da objasnis zašto je tako?
Uvek gledaj da učitavaš cele stringove, kada želiš da dobiješ ceo string, a ne karakter po karakter, jer ćes tako izbeći probleme slične navedenom, i druge, npr. vezane za to sa koliko se karaktera predstavlja prelazak u novi red u kom operativnom sistemu. Kako to da izvedeš, nije očigledno kao ručno deljenje stringa u for petlji, ali je moguće :

    string s;
    string line;
    getline(cin,line);
    istringstream iss(line);
    while(iss >> s)
    {
        for(int i = 0; i < s.size(); i++)
            s[i] = tolower(s[i]);
        sortedItems.insert(s);
    }

Kratko objašnjenje koda:

  • istringstream je klasa koja od bilo kog stringa, u ovom slučaju linije koje si učitao, pravi input stream. Jedan input stream si već koristio: cin, pa znaš kako se input stream koristi (>>)
  • Izraz iss >> s se, pored toga što se u njemu učitava s, “može tumačiti kao” 1 false ako je prilikom korišćenja stream-a iss došlo do neke greške (kraj fajla ili neka druga greška), odnosno true ako nije. Zbog toga, nakon što učitamo sve stringove iz linije, i probamo da učitamo još jedan, u iss-u će doći do greške End Of File iako se ne radi o fajlu, i izraz će vratiti false, pa ćemo izaći iz petlje

1iss >> s nije bool, ali to sada nije važno, jer se ovde ponaša kao bool.

Nadam se da te nisam dodatno ubunio. Kažu mi da se to nekad desi kada objašnjavam nešto ljudima.

Sve najbolje :wink:

2 Likes
4

@zDule98 , @DuX , hvala na pomoci! Zadatak uspesno zavrsen! :smiley: