더 Fancy한 코드가 과연 더 좋은 코드일까?

오늘자(20/08/22) LeetCode challenge를 풀다가 예전부터 생각했던 글을 쓰기로 마음먹었다.

아래 문제를 보시라

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.
You may return any answer array that satisfies this condition.

Example 1:
Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

그리고 아래 코드는 python기준으로 가장 많은 vote를 받은 방법이다

class Solution:
    def sortArrayByParity(self, A: List[int]) -> List[int]:
        return sorted(A, key = lambda x : x%2)

lambda를 key 인자로 주어 sorted를 활용하는 방식으로 단 한줄만에 조건을 만족시킨 멋있는 코드라고 생각한다

그리고 아래와 같은 방법도 있다

class Solution:
    def sortArrayByParity(self, A: List[int]) -> List[int]:
        begin, end = 0, len(A) - 1
        
        while begin <= end:
            if A[begin] % 2 == 0:
                begin += 1
            else:
                A[begin], A[end] = A[end], A[begin]
                end -= 1
        return A

첫번째 방법에 비해 7줄이나 더 긴데다가 기본연산자와 반복문만 사용하여 한눈에 보기에 딱 멋있어 보이지는 않는다.

그렇지만 과연 멋있는코드가 더 효율적일까?

• python의 sorted, list.sort() 함수는 Timsort알고리즘을 사용한다. Timsort의 시간복잡도는 O(nlogn)이므로 첫 번째 솔루션의 시간복잡도는 O(nlogn)이 된다.

• 두 번째 솔루션의 경우 루프 한 번만 돌기 때문에 시간복잡도는 O(n)이 된다

실제로 두 솔루션의 실행 시간은 꽤나 차이가 난다

첫 번째 솔루션

두 번째 솔루션

짧고 단순하고 중급 이상의 테크닉을 사용한 코드가 더 인기있는 경향이 있지만(특히 python쪽이 더 그런것 같다. 언어 태생 자체가 심플함을 추구했기 때문에 그럴지도) 과연 어느쪽이 더 효과적인지는 한 번 생각해 볼 문제이다.

참고로 나는 아래같은 방식을 가장 좋아한다

class Solution:
    def sortArrayByParity(self, A: List[int]) -> List[int]:
        even = []
        odd = []
        
        for n in A:
            if n%2:
                odd.append(n)
            else:
                even.append(n)
                
        return even+odd

메모리 좀 더 쓰면 어떠하리 읽기 편하면 장땡인것을...