Code Wars 23: Sum Groups

문제설명

Given an array of integers, sum consecutive even numbers and consecutive odd numbers. Repeat the process while it can be done and return the length of the final array.

요약
짝수나 홀수가 연속으로 구성 되어있는 경우 해당 연속된 짝수 혹은 홀수의 합을 구하여 재정렬하라. 재정렬 후에도 연속된 짝수나 홀수가 존재하는 경우 똑같은 과정을 거쳐 연속된 짝수 혹은 홀수가 없을 때 까지 재정렬하고 완성된 배열의 길이(length)를 return 해라

제한사항

None

입출력 예시

[2, 1, 2, 2, 6, 5, 0, 2, 0, 5, 5, 7, 7, 4, 3, 3, 9]
[2, 1, 10(2+2+6), 5, 2(0+2+0), 24(5+5+7+7), 4, 15(3+3+9)] #1회 정렬
[2, 1, 10, 5, 30(2+24+4), 15] #2회 정렬(더이상 연속된 짝수나 홀수 없음)
return 6

풀이

is_even = lambda x : x % 2 == 0 
def sum_groups(arr):
    pointer = [arr[0]]
    result = []
    for v in arr[1:]:
        if is_even(pointer[-1]) == is_even(v):
            pointer.append(v)
        elif is_even(pointer[-1]) != is_even(v):
            result.append(sum(pointer))
            pointer = [v]
    result.append(sum(pointer))
    
    return len(result) if result == arr else sum_groups(result)

1. 짝수 판별용 함수인 is_even을 만듭니다.
2. pointer는 연속된 짝수(or홀수)가 나오는 경우 합산된 값을 구하기 위해 존재하는 임시 리스트입니다.
3. for loop를 돌 때 모든 요소들은 우선 pointer에 담기게 됩니다. 초기값인 arr[0]이 담겨진 상태로 for loop가 시작됩니다.
4. 분기처리는 딱 두가지입니다.
   포인터의 담긴 마지막 수와 연속된 짝수or홀수 인지 아닌지 입니다. 연속된 수 일경우 pointer에 담깁니다. 연속된 수가 아닌 경우 pointer의 합산값을 result에 담습니다. 그리고 포인터는 새로운 요소를 담습니다.
5. for loop가 끝나면 포인터에 무조건 숫자가 담겨있으므로 이를 result에 더해줍니다.
   이로써 재정렬 1회분이 끝나게 됩니다.
6. 재정렬 처리가 끝난 후 처음에 인수로 받은 리스트와 재정렬 처리가 완료된 리스트가 똑같은 경우 더 이상 재정렬이 필요없으므로 len(result)를 반환합니다. 다른 경우에는 재귀로 다시 한번 재정렬 처리를 해줍니다. 반복되면서 결국에는 최종값이 반환되게 됩니다.

다른풀이

from itertools import groupby

def sum_groups(arr):
    newarr = [sum(j) for i,j in groupby(arr, key = lambda x: x % 2 == 0)]
    return len(newarr) if newarr == arr else sum_groups(newarr)

제 풀이에서 1 ~ 5번까지의 과정을 itertools의 groupby함수 + 리스트컴프리헨션을 통해 구현했습니다. itertools의 경우 combination등 다양한 내장함수를 지원하는데 이 기회에 배워두는것도 좋은 알고리즘 풀이법을 작성하는데 도움이 될 것 같네요.