[C++/Debugging] Messages Order

문제

Messages Order | HackerRank

메세지를 생성하고, 순서가 보존되지 않는 네트워크에서 송신자가 메세지를 보낸 순서대로 수신자에게 출력하도록 Message 클래스와 MessageFactory 클래스의 구현을 마무리하는 문제입니다.

풀이

class Network {
public:
    static void send_messages(vector<Message> messages, Recipient& recipient) {
    // simulates the unpredictable network, where sent messages might arrive in unspecified order
        random_shuffle(messages.begin(), messages.end());         
        for (auto msg : messages) {
            recipient.receive(msg);
        }
    }
};

Network 클래스의 멤버 함수인 send_messages 에서 메세지의 순서를 섞는 동작을 하고 있습니다.

따라서, 뒤죽박죽인 순서를 다시 보낸 순서에 맞게 정렬할 필요가 있습니다.

class Recipient {
public:
    Recipient() {}
    void receive(const Message& msg) {
        messages_.push_back(msg);
    }
    void print_messages() {
        fix_order();
        for (auto& msg : messages_) {
            cout << msg.get_text() << endl;
        }
        messages_.clear();
    }
private:
    void fix_order() {
        sort(messages_.begin(), messages_.end());
    }
    vector<Message> messages_;
};

정렬하는 동작은 Recipient 클래스의 멤버 함수인 fix_order 가 수행하고 있습니다.

Algorithm 라이브러리의 sort 함수를 사용해서 정렬을 하고 있는 모습입니다.

그러나 Recipient 클래스를 수정할 수 없으므로, 정렬하는 방식을 바꿀 수는 없습니다.

따라서, sort 함수의 동작을 이해하고 바꿔줄 필요가 있습니다.

template< class RandomIt >
void sort( RandomIt first, RandomIt last );		// (1)

...
1) Elements are compared using operator<.
...
출처: std::sort | cppreference.com

주어진 코드에서 사용된 sort 함수는 비교 연산자, '<'를 사용하여 각 요소를 비교함으로써 정렬을 수행합니다.

현재 sort 는 Message 클래스의 객체를 인수로 전달받고 있으므로, 비교 연산자가 정상적으로 수행할 수 없습니다.

따라서 '<' 연산자가 Message 클래스에 대해 동작할 수 있도록 오버로딩을 해줘야 합니다.

class Message {
public: 
    Message() {}
    
    ...
    
    bool operator<(const Message &msg2) {     		//Overload operator< function
        if (this->order_ < msg2.order_) return true;    //Compare the order of message
        else return false;
    }
private:
    string text_;
    int order_;
};

Message 클래스의 멤버 함수로 오버로딩을 해주었습니다.

메세지의 순서를 저장하는 변수인 order_ 를 비교하여 비교 연산이 가능하도록 구현했습니다.

이로 인해 sort 함수에서 비교 연산자가 정상적으로 수행하고, 메세지의 순서를 기준으로 정렬을 수행합니다.

전체 코드

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

using namespace std;

static int ORDER = 0;	//For saving the order of sent messages

class Message {
public: 
    Message() {}
    Message(const string& text)
    : text_(text), order_(ORDER++) {}	//Initialize text and order of message
    const string& get_text() {
        return text_;
    }
    bool operator<(const Message &msg2) {     		//Overload operator< function
        if (this->order_ < msg2.order_) return true;	//Compare the order of message
        else return false;
    }
private:
    string text_;
    int order_;
};

class MessageFactory {
public:
    MessageFactory() {}
    Message create_message(const string& text) {
        return Message(text);	//Use constructor of Message Object
    }
};

class Recipient {
public:
    Recipient() {}
    void receive(const Message& msg) {
        messages_.push_back(msg);
    }
    void print_messages() {
        fix_order();
        for (auto& msg : messages_) {
            cout << msg.get_text() << endl;
        }
        messages_.clear();
    }
private:
    void fix_order() {
        sort(messages_.begin(), messages_.end());
    }
    vector<Message> messages_;
};

class Network {
public:
    static void send_messages(vector<Message> messages, Recipient& recipient) {
    // simulates the unpredictable network, where sent messages might arrive in unspecified order
        random_shuffle(messages.begin(), messages.end());         
        for (auto msg : messages) {
            recipient.receive(msg);
        }
    }
};



int main() {
    MessageFactory message_factory;
    Recipient recipient;
    vector<Message> messages;
    string text;
    while (getline(cin, text)) {
        messages.push_back(message_factory.create_message(text));
    }
    Network::send_messages(messages, recipient);
    recipient.print_messages();
}

참고

• std::sort | cppreference.com