937 Reorder Data in Log Files

937. Reorder Data in Log Files

문제

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.

• 로그 배열이 주어진다
  • 문자열 로그: 영어 소문자로만 구성
  • 숫자 로그: 숫자로만 구성
• 문자열 로그가 숫자 로그보다 앞서 온다
• 문자열 로그는 사전순을 따른다. 만약 내용이 같다면, 아이디의 사전순으로 정렬한다
• 숫자 로그는 상대 순서를 유지한다. 즉 원래 순서 유지.

조건

• 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.

예제

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"]

해결

생각

• 속도를 빠르게 하자!라는 생각으로 byte를 가져와서 더해버렸다
• 하지만 “def”보다 “abcd”다 더 많은 문자를 가지고 있으므로 abcd가 뒤에 오게 된다!! 멍청하긴…

System.out.printf("%d\n", "def".chars().reduce(0, Integer::sum)); // 303
System.out.printf("%d\n", "abcd".chars().reduce(0, Integer::sum)); // 394

• 그 다음에는 로그 + 아이디로 아이디를 뒤로 보내서 로그 문자열 순으로 정렬하고, 겹치면 아이디 순으로 정렬되겠지? 라는 순진한 생각을 했다. 어림도 없지…

• 이러면 “let1 abcd”과 “z abc”가 있을 때 “abcdlet1”과 “abcz”가 되어 “abc”가 먼저 와야 하는데 뒤로 가게 돼버린다. 필요에 따라 데이터 조작이 필요하지만, 데이터 자체를 근본적으로 바꿔서 저장하는 건 리스크가 크다!라는 건 익히 알고 있지만 또 같은 실수를 저질렀다.

• 순서를 유지할 필요가 있어서 TreeMap이란 자료 구조를 쓰기로 했다. 또 같은 문자열인 경우 다시 한번 정렬해야 하므로, TreeMap<String, TreeMap<String, String>>으로 데이터 구조를 구상했다
  • 정렬해야하는 것은? 아이디 + 로그 중 로그다. 그래서 로그를 키로 잡았다.
  • 로그가 같은지 여부는? TreeMap의 containsKey를 활용
  • 로그가 같으면? 아이디로 비교해야 한다. 그래서 하위의 TreeMap의 키는 id, 그 값은 원본 로그로 했다. 결국 원본 로그를 되돌려 줘야 하니까!

코드

public String[] reorderLogFiles(String[] logs) {
    String[] answer = new String[logs.length];
    String[] digits = new String[logs.length];
    TreeMap<String, TreeMap<String, String>> letters = new TreeMap<>();
    int answerIdx = 0;
    int digitsIdx = 0;
    for (String log : logs) {
        int idxOfFirstSpace = log.indexOf(' ');
        String logDetail = log.substring(idxOfFirstSpace + 1);
        // 0 = 48, 9 = 57 | A = 65, Z = 90 | a = 97, z = 122
        if (48 <= logDetail.charAt(0) && logDetail.charAt(0) <= 57) {
            digits[digitsIdx++] = log;
        } else {
            // logDetail 간의 길이가 다르고, id가 뒤에 붙으면서 id가 순서에 영향을 주게 된다
            if (! letters.containsKey(logDetail)) {
                TreeMap<String, String> subLetters = new TreeMap<>();
                subLetters.put(log, log);
                letters.put(logDetail, subLetters);
                continue;
            }
            letters.get(logDetail).put(log, log);
        }
    }
    for (TreeMap<String, String> subLetters : letters.values()) {
        for (String subLetter : subLetters.values()) {
            answer[answerIdx++] = subLetter;
        }
    }
    for (int i = 0; i < digitsIdx; i++) {
        answer[answerIdx++] = digits[i];
    }

    return answer;
}

결과

Runtime: 2 ms, faster than 99.86% of Java online submissions for Reorder Data in Log Files.
Memory Usage: 39 MB, less than 93.37% of Java online submissions for Reorder Data in Log Files.

리트코드 다른 코드

public String[] reorderLogFiles(String[] logs) {
    int insert_pt = logs.length - 1; // where to put the next digit logs
    while (insert_pt >= 0 && Character.isDigit(logs[insert_pt].charAt(logs[insert_pt].length() - 1))) {
      --insert_pt;
    }
    for (int i = insert_pt; i >= 0; --i) {
        String str = logs[i];
        if (Character.isDigit(str.charAt(str.length() - 1))) {
            String temp = logs[insert_pt];
            logs[insert_pt] = logs[i];
            logs[i] = temp;
            --insert_pt;
        }
    }
    
    Arrays.sort(logs, 0, insert_pt + 1, (x,y)->{
        int start_x = 0;
        while (x.charAt(start_x++) != ' ');
        int start_y = 0;
        while (y.charAt(start_y++) != ' ');
        for (; start_x < x.length() && start_y < y.length(); ++start_x, ++start_y) {
            int comp = Character.compare(x.charAt(start_x), y.charAt(start_y));
            if (comp != 0) return comp;
        }
        
        if (start_x == x.length() && start_y == y.length()) {
            return x.compareTo(y);
        } else return start_x < x.length() ? 1 : -1;
    });
    
    return logs;
}

• Arrays의 sort를 사용