C++ ] leetCode 937 - Reorder Data in Log Files

 

 

리트코드 937번 문제

 

You are given an array of logs. Each log is a space-delimited string of words, where the first word is the identifier. There are two types of logs:

 

• Letter-logs: All words (except the identifier) consist of lowercase English letters.
• Digit-logs: All words (except the identifier) consist of digits.

 

 

Reorder these logs so that:

1. The letter-logs come before all digit-logs.
2. The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.
3. The digit-logs maintain their relative ordering. Return the final order of the logs.

 

 

Example 1:

• Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
• Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]
• Explanation: The letter-log contents are all different, so their ordering is "art can", "art zero", "own kit dig". The digit-logs have a relative order of "dig1 8 1 5 1", "dig2 3 6".

 

Example 2:

• Input: logs = ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
• Output: ["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]

 

 

Constraints:

• 1 <= logs.length <= 100
• 3 <= logs[i].length <= 100
• All the tokens of logs[i] are separated by a single space.
• logs[i] is guaranteed to have an identifier and at least one word after the identifier.

 

문제에 등장하는 로그는 두 종류가 있다. 문자열을 공백으로 구분한다고 했을 때 tokens[0]은 identifier이고, letter-logs는 identifer를 제외한 모든 단어가 알파벳 소문자이며 digit-logs는 identifier를 제외한 모든 단어가 숫자이다. 모든 letter-logs는 digit-logs 앞에 오고, letter-logs는 사전적 순서를 유지하며, digit-logs는 원래의 상대적 순서를 유지하면 된다.

 

1. 조건에 맞게 재배치한 문자열을 담을 ret 벡터와 identifier 뒤에 등장하는 문자열을 담을 contents 벡터를 선언하고 미리 공간을 할당해 둔다.

 

2. letter-logs와 digit-logs의 인덱스를 저장해둘 letterIdx, digitIdx 벡터를 선언한다.

 

3. 모든 logs에 대해 첫번째로 등장하는 공백 다음 위치부터 stubstr을 추출해 contens에 저장하고 contents 첫 문자가 digit이면 digitIdx에 해당 인덱스를 추가하고 digit이 아닌 경우엔 letterIdx에 추가한다.

 

4. letterIdx는 sort함수를 통해 직접 비교함수를 정의하여 정렬한다. 모든 외부 변수를 캡쳐해 contens와 logs에 접근 가능하도록 하고 letterIdx 두 원소에 따른 contents가 같지 않은 경우 contents의 사전적 대소비교 결과를 리턴하고 contents가 같은 경우에는 logs의 사전적 대소비교 결과를 리턴한다.

(실제로 로그의 내용은 똑같고 identifier만 다를 때 identifier의 사전적 순서로 정렬해야 정답으로 인정해주는 케이스가 등장했다.)

 

5. 원본 데이터의 사전적 순서에 따라 정렬된 letterIdx와 기존의 등장 순서를 유지하고 있는 digitIdx를 사용해 ret 벡터의 내용을 채우고 반환한다.

 

class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        vector<string> ret(logs.size());
        vector<string> contents(logs.size());
        vector<int> letterIdx;
        vector<int> digitIdx;

        for(int i = 0; i < logs.size(); i++) {
            size_t spacePos = logs[i].find(' ');
            contents[i] = logs[i].substr(spacePos + 1);
            if(isdigit(contents[i][0])) {
                digitIdx.push_back(i);
            }
            else {
                letterIdx.push_back(i);
            }
        }

        sort(letterIdx.begin(), letterIdx.end(), [&](const int &a, const int &b){ 
            if(contents[a] != contents[b]) return contents[a] < contents[b];
            else return logs[a] < logs[b]; });

        int retIdx = 0;
        for(auto &idx : letterIdx) {
            ret[retIdx++] = logs[idx];
        }

        for(auto &idx : digitIdx) {
            ret[retIdx++] = logs[idx];
        }
        
        return ret;
    }
};