3
\$\begingroup\$

I have started doing Kattis challenges from their website. For now I am still at the low complexity ones.

The first line of input contains a single positive integer T≤50 indicating the number of test cases. The first line of each test case also contains a single positive integer n indicating the number of elements available for the test case.

Elements only contain lowercase letters, have at least one letter, and do not contain spaces.

The number elements for a test case is at most 100 and each element contains no more than 20 characters.

For each test case, I have to output a single line containing a single integer that is the number of distinct elements found in the specific test case.

To view the challenge follow this link: I've Been Everywhere, Man

Sample input:

2
7
saskatoon
toronto
winnipeg
toronto
vancouver
saskatoon
toronto
3
edmonton
edmonton
edmonton

Sample output:

4
1

Here is the code:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using std::cin;
using std::cout;
using std::vector;
using std::string;

int main()
{
    int testCasesCount = 0, tripsCount = 0;
    vector<string> trips;
    vector<int> testCasesResults;

    cin >> testCasesCount;

    for (int i = 0; i < testCasesCount; i++) {
        cin >> tripsCount;

        string destination;
        int uniqueCount = 0;
        for (int j = 0; j < tripsCount; j++) {
            cin >> destination;

            if (std::find(trips.begin(), trips.end(), destination) == trips.end())
                trips.push_back(destination);
        }

        testCasesResults.push_back(uniqueCount);
    }

    for (unsigned int i = 0; i < testCasesResults.size(); i++)
        cout << testCasesResults.at(i) << "\n";

    return 0;
}

The code is working fine, BUT it's kind of ugly, at least that's how I see it.

My first question is to ask if there is a better way to check if an array/vector contains a certain element?

And the second question - can someone give me some tips as to what I can improve and what will be a good idea to avoid?

\$\endgroup\$
1
\$\begingroup\$

As you yourself hinted in the question title, you should be using a set. Discarding duplicates using a set is easier and more efficient than using a vector.

\$\endgroup\$
  • \$\begingroup\$ I see, it is exactly what I needed here. I have changed it, now for trips I am using a set of strings and for testCasesResults - a regular array. \$\endgroup\$ – B Mutev Dec 14 '16 at 17:21
1
\$\begingroup\$

If you want to improve things even further, don't add the results to a vector, just print them out as you get them:

int testCasesCount = 0 , tripsCount = 0;
set<string> trips;
cin >> testCasesCount;

for ( int i = 0; i < testCasesCount; i++ ) {
    cin >> tripsCount;
    string destination;
    for ( int j = 0; j < tripsCount; j++ ) {
        cin >> destination;
        //If destination is a duplicate, emplace will just fail.
        trips.emplace( destination );
    }
    cout << trips.size() << '\n';
    trips.clear();
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.