Codewars Snail 알고리즘

2019-07-22

예시

array = [[1,2,3],
         [4,5,6],
         [7,8,9]]
snail(array) #=> [1,2,3,6,9,8,7,4,5]

몰랐는데 사실 유명한 알고리즘이다.

다른 알고리즘은 아예 달팽이가 가면서 배열을 만들던데 이건 이미 있는 배열을 순서대로 훑기만 하면 된다.

1시간동안 이해 안되다가 직접 다 출력하고 손으로 풀어보니 이해가 됐다.

알고리즘 자체는 아래와 같고 이해가 안되서 결과값 출력하려고 작성한 코드는 조금 더 밑에 있다.

풀이

def snail(array):
    results = []
    while len(array):
        # go right
        results += array[0]
        del array[0]

        if len(array):
            # go down
            for i in array:
                results += [i[-1]]
                del i[-1]

            # go left
            if array[-1]:
                results += array[-1][::-1]
                del array[-1]

            # go top
            for i in reversed(array):
                results += [i[0]]
                del i[0]

    return results

이 알고리즘을 이해하는데 핵심은 리스트를 잘 다룰줄 아느냐 인것같다.

[::-1]이 역방향으로 훑는 기능이라는 것도 알았고 reversed(array)도 이해했다.

하지만 눈으로 보는 것보다 공책에 하나하나 써가면서 이해하는게 훨씬 도움이됐다.

귀찮기는 하지만 이게 제일 좋다.

def snail(array):
    results = []
    while len(array):
        # go right
        results += array[0]
        del array[0]
        print("array:", data2)
        print("results:", results)

        if len(array):
            # go down
            for i in array:
                results += [i[-1]]
                del i[-1]
                print("array:", data2)
                print("results:", results)    

            # go left
            if array[-1]:
                results += array[-1][::-1]
                del array[-1]
                print("array:", data2)
                print("results:", results)

            # go top
            for i in reversed(array):
                print("i:",i)
                results += [i[0]]
                del i[0]
                print("array:", data2)
                print("results:", results)

    return results

data2 = [[1, 2, 3, 4],
        [12, 13, 14, 5],
        [11, 16, 15, 6],
        [10, 9, 8, 7]]


print(snail(data2))

결과값

array: [[12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]
results: [1, 2, 3, 4]
array: [[12, 13, 14], [11, 16, 15, 6], [10, 9, 8, 7]]
results: [1, 2, 3, 4, 5]
array: [[12, 13, 14], [11, 16, 15], [10, 9, 8, 7]]
results: [1, 2, 3, 4, 5, 6]
array: [[12, 13, 14], [11, 16, 15], [10, 9, 8]]
results: [1, 2, 3, 4, 5, 6, 7]
array: [[12, 13, 14], [11, 16, 15]]
results: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
i: [11, 16, 15]
array: [[12, 13, 14], [16, 15]]
results: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
i: [12, 13, 14]
array: [[13, 14], [16, 15]]
results: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
array: [[16, 15]]
results: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
array: [[16]]
results: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
array: []
results: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]