[LeetCode] 937. Reorder Data in Log Files (JS)

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

Reorder Data in Log Files - LeetCode

핵심 아이디어

• letterLogs, digitLogs 두 배열로 나눈 뒤 합친다
• js string 비교는 String.localeCompare()로 할 수 있다

 

복잡도

• 시간 복잡도: O(N^2*logN)
  
  • sort() NlogN * slice() N
• 공간 복잡도: O(N)
  
  • letterLogs, digitLogs 배열

 

설명

1. letter logs는 digit logs 앞에 온다

2. letter logs는 content (제일 처음 identifier 제외한 것) 알파벳 순서대로 정렬하고 content 같으면 identifier 순으로 정렬한다

3. digit log는 입력 순서대로 쓴다

 

위 조건대로 정렬하는 문제이다. 따라서

 

1. letterLogs와 digitLogs 분리

2. letterLogs는 content 만 분리해서 알파벳순 비교, 같으면 identifier 비교

3. digit log는 그대로 쓴다

3-1. filter는 ECMAScript spec 상 순서 유지를 보장한다고 하니 filter한 것 그대로 쓰면 된다

 

이렇게 구현하면 된다.

여담으로, 최적화가 의미 없는 문제인 것 같다. 애초에 조건부터가 시간 제한을 걸어놓지 않고, 개수도 length도 100개 이하다. split() 대신 slice()를 쓰면 런타임이 줄어들까 했지만 알고보니 slice()도 O(N) 시간이어서 의미는 없었다.

마찬가지로 filter()를 for...of로 바꿔서 반복문 한 번만 돌게 해도 최적화하는 의미가 없었다. 그러면 나같으면 filter()로 쓸 것이다. 함수형이 더 알아보기도 쉽고 수정하기도 쉬우니 말이다. medium 문제인데 생각할 거리도 없고 easy 문제보다 더 쉬웠다. 이러니 문제에 dislike가 더 많이 달렸나보다

 

코드 (Javascript)

/**
 * @param {string[]} logs
 * @return {string[]}
 */
const isDigit = (str) => !isNaN(Number(str));
const getContent = (log) => {
    const content = log.slice(log.indexOf(" ") + 1);
    return content;
}

var reorderLogFiles = function(logs) {
    const letterLogs = logs.filter(log => !isDigit(log.split(" ")[1])).sort(
       (logA, logB) => {
           const contentA = getContent(logA);
           const contentB = getContent(logB);
           
           const contentCompare = contentA.localeCompare(contentB);
           
           if(contentCompare === 0) {
               return logA.localeCompare(logB);
           }
           return contentCompare;
       });
    const digitLogs = logs.filter(log => isDigit(log.split(" ")[1]));
    
    return [...letterLogs, ...digitLogs]
};