[Leet Code] 937. Reorder Log Files(로그 파일 재정렬)

 

로그를 재정렬하는 문제예요. 현업 프로젝트 코드에서도 로그는 거의 모든 부분에서 수집하기 때문에 그걸 처리하는 센스를 보는 문제라고 할 수 있어요. 난이도가 쉬운 문제인데 책에서 주어진 정보가 매우 부족하고 조건이 부실해서 책을 기준으로 문제를 풀었더니 예외처리에 시간이 오래 걸렸어요. <파이썬 알고리즘 인터뷰>에서 제공하는 문제 정보는 항상 조건에 대한 정보가 부실하다고 느껴요. 반례의 상황 등에서요. 오히려 풀이를 보면서 "이렇게 풀이하는 걸 보면 문제 조건이 이렇게 제한될 수밖에 없구나"라고 판단했어요. <파이썬 알고리즘 인터뷰>에 나오는 풀이 상으로는 숫자 로그는 숫자만 나오고, 문자 로그는 문자만 나와요. 혼용될 수 없지만 조건에 없었어요(그래도 덕분에 혼용되는 조건이라는 발전된 문제를 생각해볼 수 있었고 아래 고민 섹션에 코드를 올렸어요).

반면 LeetCode에서는 정확히 로그의 타입이 두개라고 명시가 돼요.

 

LeetCode 문제 조건

앞으로 LeetCode의 문제는 책을 기준으로 하는게하는 게 아니라 홈페이지의 문제를 기준으로 하는 게 좋을 것 같아요. 스터디를 할 때에도 팀원 모두가 책 설명을 이해 못 한 문제도 있었어요. 혹시 <파이썬 알고리즘 인터뷰>를 읽으시는 다른 분들도 같은 실수를 반복할 수 있어 실수를 공유했어요 :]

 

📝 풀이

def my_solution(logs: [str]):
    letter_logs, numeric_logs = [], []
    for log in logs:
        if log.split()[1].isdigit():
            numeric_logs.append(log)
            continue
        letter_logs.append(log)
    return sorted(letter_logs, key=lambda x: (x.split()[1:], x.split()[0])) + numeric_logs

 

이러한 풀이가 나올 수 있는 건, LeetCode에 나오는 것처럼 로그에 숫자, 문자 혼용이 없다는 조건 하에서에요. log.split()[1]은 정확히 이야기하면 식별자를 제외한 로그의 첫 번째 요소예요. 

예를 들면, 로그가 "dig1 8 1 5 1"일 경우 숫자 8이 되고, "let1 art car"의 경우 문자열 "art"가 되요. 즉, 로그의 요소 중 한 개만 확인하더라도 그 로그의 타입을 판단할 수 있기 때문에 위와 같이 조건을 작성했어요. 

🧐 고민

1. 파이썬에는 숫자 판별을 위한 메서드가 여러개 있어요. isdigit, isnumeric, isdecimal인데 그 차이는 검색 해보면 좋을 것 같아요! 이 문제에서는 특별한 조건이 없어 세 함수 중 어떤 것을 사용해도 무방해서 isdigit을 사용했어요.

 

2. 문자열 정렬에서 기본적으로 숫자가 문자보다 앞에 와요. 그래서 문자가 숫자보다 앞에 오게 할 정렬 방법을 선택해야 하고, 문제에서는 리스트를 두 개 사용하는 것으로 해결했어요. 같은 풀이 방식이라면 공간 복잡도를 줄이는 것이 좋지만 작은 메모리를 아끼기 위해 문제 풀이에 영향을 주는 건 스스로 고쳐야 할 습관이라고 판단돼요. 변수 만드는 것을 두려워하지 말아야 해요.

 

3. isdigit(), isalpha()의 공백 처리

"123".isdigit() # True
"abc".isalpha() # True

"3 6".isdigit() # False
"a b c".isalpha() # False

공백이 들어가는 순간 두 메소드 모두 False를 반환해요. 그래서 공백이 섞인 문자열을 확인하고 싶다면 replace(" ", "") 메서드나 split 후 다시 join 하는 등의 공백 제거 후 판단해야 해요.

 

4. 책을 통해서 문제를 읽었을 때, 로그에 숫자와 문자가 혼용될 경우도 고려해야 한다고 판단해서 문자가 먼저 오게 하는 방법을 생각했어요. 이 부분은 단순히. sort(key=lambda...)로 처리할 수 없어서 customized_sort라는 메서드를 만들었어요. 숫자 로그 역시 정렬되는 메서드예요.

def customized_sort(first_element: str, second_element: str) -> (str, str):
    max_index = len(first_element) if len(first_element) < len(second_element) else len(second_element)
    index = 0
    while index < max_index:
        if first_element[index] == second_element[index]:
            index += 1
            continue
        if first_element[index].isalpha() and second_element[index].isdigit():
            return first_element, second_element
        elif first_element[index].isdigit() and second_element[index].isalpha():
            return second_element, first_element
        return first_element, second_element if first_element[index] < second_element[
            index] else second_element, first_element
    return first_element, second_element

문제 풀이에 전혀 도움이 안 되는 코드이지만 혹시나 현업에서 비슷한 고민을 하시는 분 등 비슷한 고민을 하시는 분들을 위해 공유해요. 두 문자열을 비교할 때 비교는 더 짧은 걸 기준으로 했어요.

 

책에 나오는 조건에서 "문자열이 길면 뒤로 간다" 등의 추가적인 조건이 없어서 길이가 다른 상황에서 짧은 문자열을 기준으로 모든 문자열이 같다면 순서를 유지하게 만들었어요(e.g. "abcdefg" vs "abcd"는 순서 유지). 문제의 조건대로 숫자 로그는 유지하려면 조건문 한 개만 더 들어가면 돼요.

 

문자를 하나하나 확인하면서 같은 위치의 문자가 같다면 넘어가고, 다를 경우는 조건을 만들어 비교했어요.

if first_element[index].isalpha() and second_element[index].isdigit():
	return first_element, second_element
elif first_element[index].isdigit() and second_element[index].isalpha():
	return second_element, first_element

위의 비교에서 둘 중 하나만 숫자인 경우 앞에 배치하는 것으로 했어요. 사실 코드를 읽기 더 쉽게 작성하려면 여기에 boolean 값 플래그를 두고, 마지막에 sort 할 것인지 reverse sort 할 것인지를 판단하는 방식으로 작성하는 것인데 그렇게 하면 O(NlogN)이 될 것이고, 지금 위의 코드는 O(N)이라 알고리즘 문제의 특성상 효율이 더 중요하다고 판단했어요. 

 

그리고 둘 다 같이 문자나, 숫자일 경우에는 단순 비교로 반환하게 했어요. 

 

비교를 완료해도 결과가 나오지 않는 경우(e.g. "abc" vs "ab")에는 while문 안에서 return 되지 않기 때문에 마지막에 값을 순서를 유지하며 그대로 반환하게 했어요.

 

여기서 한걸음 더 나가면 List.sort(key=...)에서 key의 값에 넣을 함수를 정의하는 것도 방법도 있을 것 같아요. 일반적으로 lambda 함수를 넣는데 x: (x[0], -x[1]) 이런 식이라 조건을 잘 명세한 메서드를 구현하면 호출하는 부분에서 더 깔끔한 코드가 될 수 있지 않을까 생각해봤어요.

 

🐾 문제 링크 가기

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