[LeetCode] C++ 937. Reorder Data in Log Files

https://leetcode.com/problems/reorder-data-in-log-files/description/

 

문제

 

문제 분석

1. letter-logs와 digit-logs를 분리해서 관리하고 letter-logs 뒤에 digit-logs를 이어붙이면 되겠다고 생각

2. lettter-logs의 경우 identifier를 제외하고 나머지 부분들을 비교해서 순서를 정하고, 나머지 부분들이 모두 같은 경우에는 identifier를 기준으로 정렬

 

풀이

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

using namespace std;

// 로그 비교 함수
bool compare(string a, string b) {
    stringstream s1(a);
    stringstream s2(b);

    string temp_a;
    string temp_b;

    // 식별자를 추출
    s1 >> temp_a;
    s2 >> temp_b;

    // 식별자가 동일한 경우를 대비하여 미리 저장
    bool identifierOrder = temp_a < temp_b;

    // 로그 내용을 비교
    while (s1 >> temp_a && s2 >> temp_b) {
        if (temp_a != temp_b)
            return temp_a < temp_b;
    }

    // s1이 더 긴 경우
    if (s1 >> temp_a) {
        return false;
    }

    // s2가 더 긴 경우
    if (s2 >> temp_b) {
        return true;
    }

    // 로그 내용이 같을 경우 식별자 비교
    return identifierOrder;
}

class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        int len = logs.size();

        vector<string> letterLogs;  // 문자 로그를 저장할 벡터
        vector<string> digitLogs;   // 숫자 로그를 저장할 벡터

        string word;

        // 로그를 문자 로그와 숫자 로그로 분리
        for (int i = 0; i < len; ++i) {
            stringstream ss(logs[i]);

            ss >> word; // 식별자 부분을 건너뜀
            ss >> word;
            if (isdigit(word[0])) {
                digitLogs.push_back(logs[i]); // 숫자 로그로 분류
            } else {
                letterLogs.push_back(logs[i]); // 문자 로그로 분류
            }
        }

        // 문자 로그를 비교 함수에 따라 정렬
        sort(letterLogs.begin(), letterLogs.end(), compare);

        // 숫자 로그를 문자 로그 뒤에 병합
        letterLogs.insert(letterLogs.end(), digitLogs.begin(), digitLogs.end());
        return letterLogs;
    }
};

int main() {
    Solution solution;
    vector<string> logs = {"dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"};
    vector<string> result = solution.reorderLogFiles(logs);

    for (const string& log : result) {
        cout << log << endl;
    }

    return 0;
}

compare 함수가 두 요소의 순서를 결정하는 방식

• true를 반환하면, 첫 번째 요소가 두 번째 요소보다 작다고 간주하고 순서를 유지
• false를 반환하면, 첫 번째 요소가 두 번째 요소보다 크거나 같다고 간주하고 순서를 바꿈.

 

빠른 풀이

내 풀이의 경우 한 부분마다 나눠서 비교를 하고 끝까지 비교가 끝난 후에 식별자를 비교한다 이런 식이었는데, 그냥 식별자가 아닌 것과 식별자로 분리한 뒤에 식별자가 아닌 것에 대해서 한 번에 compare한 뒤에, 만약 같으면 식별자를 비교하는 방식으로 하면 더 빠르게 가능했다.

class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        vector<string> digitLogs, ans;
        vector<pair<string, string>>letterLogs;

        for (auto &log: logs){
            int i = 0;
            while(log[i] != ' ') i++;
            if(isdigit(log[i+1]))
                digitLogs.push_back(log);
            else{
                letterLogs.emplace_back(log.substr(0,i), log.substr(i));          
            }
        }

        sort(letterLogs.begin(), letterLogs.end(), [&](auto &a, auto &b){
            return a.second == b.second ? a.first < b.first : a.second < b.second;
        });

        for(auto &letterLog: letterLogs){
            ans.emplace_back(letterLog.first + letterLog.second);
        }

        ans.insert(ans.end(), digitLogs.begin(), digitLogs.end());
        return ans;
    }
};