Python으로 로그 파일 데이터 재정렬하기: 문자 로그·숫자 로그 정렬 알고리즘

문제 개요

로그 문자열 배열이 주어졌다고 가정해 보겠습니다. 배열의 각 항목은 공백으로 구분된 단어들로 이루어져 있으며, 첫 번째 단어는 항상 영숫자(alphanumeric) 식별자(identifier)입니다. 식별자 뒤에 오는 단어들은 아래 두 가지 유형 중 하나에 속합니다.

식별자 뒤의 모든 단어가 소문자 알파벳으로만 구성된 경우
식별자 뒤의 모든 단어가 숫자로만 구성된 경우

첫 번째 유형을 문자 로그(letter-log), 두 번째 유형을 숫자 로그(digit-log)라고 부릅니다. 또한 모든 로그는 식별자 뒤에 최소 한 개 이상의 단어를 포함하는 것이 보장됩니다.

재정렬 규칙

로그 배열은 다음 규칙에 따라 재정렬해야 합니다.

모든 문자 로그는 어떤 숫자 로그보다도 앞에 위치해야 합니다.
문자 로그끼리는 식별자를 제외한 본문 내용을 기준으로 사전순(lexicographical order)으로 정렬하며, 내용이 동일한 경우에는 식별자를 기준으로 순서를 결정합니다.
숫자 로그는 입력받은 원래 순서를 그대로 유지합니다(안정 정렬).

최종적으로 재정렬된 로그 배열을 반환하면 됩니다.

입출력 예시

예를 들어 입력이 다음과 같다고 해보겠습니다.

logs = ["dig1 9 2 5 2", "let1 art can", "dig2 4 8", "let2 own kit dig", "let3 art zero"]

위 입력에 대한 출력은 다음과 같습니다.

["let1 art can", "let3 art zero", "let2 own kit dig", "dig1 9 2 5 2", "dig2 4 8"]

"art can"과 "art zero"가 사전순으로 앞부분을 차지하고 "own kit dig"가 그 뒤를 따르며, 두 개의 숫자 로그는 원래 순서대로 마지막에 배치된 것을 확인할 수 있습니다.

해결 접근 방법

이 문제는 문자 로그와 숫자 로그를 먼저 분리한 뒤, 문자 로그만 정렬해서 다시 합치는 방식으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.

문자 로그를 담을 리스트(letters)와 숫자 로그를 담을 리스트(digits)를 준비합니다.
각 로그를 순회하면서 식별자와 본문을 분리합니다.
본문의 첫 단어가 숫자라면 해당 로그를 digits에 원본 그대로 추가합니다.
그렇지 않다면 (본문, 식별자) 형태의 튜플로 만들어 letters에 추가합니다.
letters를 정렬합니다. 파이썬의 튜플 비교 특성 덕분에 본문이 먼저 비교되고, 본문이 같으면 식별자가 비교됩니다.
정렬된 문자 로그와 숫자 로그를 순서대로 합쳐 반환합니다.

Python 구현 코드

class Solution:
    def reorderLogFiles(self, logs):
        letters = []  # 문자 로그 저장
        digits = []   # 숫자 로그 저장

        for log in logs:
            parts = log.split(' ', 1)          # 식별자와 본문 분리
            if parts[1][0].isdigit():          # 본문 첫 글자가 숫자인지 확인
                digits.append(log)
            else:
                letters.append((parts[1], parts[0]))  # (본문, 식별자)

        letters.sort()  # 본문 우선 정렬, 동률 시 식별자 순

        return [body + ' ' + identifier for body, identifier in letters] + digits


ob = Solution()
print(ob.reorderLogFiles(["dig1 9 2 5 2", "let1 art can", "dig2 4 8",
                          "let2 own kit dig", "let3 art zero"]))

실행 결과

['let1 art can', 'let3 art zero', 'let2 own kit dig', 'dig1 9 2 5 2', 'dig2 4 8']

동작 원리 자세히 살펴보기

핵심은 (parts[1], parts[0])처럼 본문을 튜플의 첫 번째 요소로 넣는 것입니다. 파이썬은 튜플을 비교할 때 첫 요소부터 순서대로 비교하기 때문에, 별도의 key 함수 없이도 "본문 우선, 동률 시 식별자"라는 정렬 조건이 자연스럽게 적용됩니다.

또한 log.split(' ', 1)처럼 최대 분할 횟수를 1로 지정하면 문자열을 딱 두 조각(식별자 / 나머지 전체)으로만 나누게 됩니다. 덕분에 분리했던 본문 단어들을 다시 합치는 불필요한 작업 없이 깔끔하게 처리할 수 있습니다.

시간 및 공간 복잡도

시간 복잡도: O(n·m + k log k) — n은 로그 개수, m은 평균 로그 길이, k는 문자 로그 개수입니다. 문자 로그 정렬이 지배적인 비용입니다.
공간 복잡도: O(n) — 문자 로그와 숫자 로그를 분류해 담기 위한 추가 리스트가 필요합니다.

이처럼 로그를 유형별로 분류한 뒤 정렬만 적용하면 되는 문제이기 때문에, 파이썬의 내장 sort()와 튜플 비교를 활용하면 매우 직관적이고 효율적으로 해결할 수 있습니다.