[C#/Codewars] Snail 후기 (4kyu)

링크: https://www.codewars.com/kata/521c2db8ddc89b9b7a0000c1

Codewars에서 4급인 Snail문제를 풀어봤다.

4급 문제 중 가장 유명한 문제이며, 난이도는 4급 중 다소 쉬운 편에 속한다. (다만 필자는 꽤나 힘겹게 풀었다.)

문제 설명:

크기 불특정의 n*n 이차원 배열을 받으면, 그 배열을 마치 달팽이 껍질의 모양과 유사하게 시계방향으로 훑으며 일자로 펴진 단일차원배열을 반환하는 함수를 짜는 문제이다.

Q. int[][]는 이차원 배열이 아니잖슴~

A.엄밀히 따지면 int[,] 이차원 배열은 아니라서 .GetLength(1)같은 함수는 못쓴다. 그 대신, 배열의 길이를 구하기 위해 array[0].Length를 쓰도록 하자.

(array.Length 또는 array.GetLength(0)은 빈 배열에서도 1을 반환하기 때문에 문제가 생긴다.)

예시:

array = [[1,2,3],

        [4,5,6],

        [7,8,9]]

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

(codewars 예시를 그대로 가져왔다.)

밑의 해법을 보기 전에 한번 풀어보길 바란다.

필자의 접근:

달팽이 껍질과 같이 한 셀씩 이동하면서 요소를 훑는 문제이기 때문에, 직관적으로 떠오르는 방법을 사용했다. 이렇게 풀고 나서 다른 풀이를 보면 현타+감탄이 보다 세게 오기 때문에 주의 바란다.

direction = ‘R’;

pos = new int[] { 0, 0 };

int length = array[0].Length;

var snailed = new int[length * length];

var map = new bool[length, length];

char형의 direction은 전역변수로 선언했다. 시작과 동시에 오른쪽으로 이동하므로 ‘R’로 초기화 한다.

pos 또한 전역변수로 선언했다. 시작 위치는 왼쪽 위이므로 { 0, 0 }으로 초기화 한다.

int[] snailed는 반환될 값을 담기 위한 배열이다.

bool[length, length]은 이미 훑은 셀로 다시 이동하는 일이 없도록 검사하기 위해 놓은 장치이다.

for (int i = 0; i < length * length; i++)

{
snailed[i] = array[pos[0]][pos[1]];

map[pos[0], pos[1]] = true;

if (!Movable(map, length))

Turn();

Move();

}

가장 중요한 for 반복문. 반복 횟수는 당연히 모든 요소를 돌아야 하기 때문에 length * length이다.

이제 return될 운명인 snailed에 하나하나 값을 넣어주기만 하면 끝이다.

array[][]의 각각의 index에 pos[0](x좌표)와 pos[1](y좌표)를 넣어 snailed에 들어갈 값을 지정한다.

map[,]의 값을 넣은 부분을 true로 바꿔주며, 루프를 한 번 돌 때마다 오른쪽으로 한 칸씩 이동해주면 된다.

하지만 계속 오른쪽으로만 가다가는 우리 앞에는 IndexOutOfRangeException만이 기다리고 있다. 이제 방법은 없는걸까?

아니다, 호랑이 굴에 들어가도 정신만 차리면 살 수 있고, 이차원 배열 안에 들어가도 Border만 잘 설정하면 살 수 있다 했다. 적절한 타이밍에 방향을 틀어줘보자.

bool Movable() 함수에서는 앞으로 이동하면 이미 훑은 요소인지, 낭떠러지인지, 아니면 이동할 수 있는 셀인지를 부울값으로 알려준다.

public static bool Movable(bool[,] map, int length)

{
bool movable = true;

switch (direction)

{

case ‘R’ :

if (pos[1] + 1 == length ||

   map[pos[0], pos[1] + 1)

movable = false;

break;

…

}

return movable;

}

switch문을 사용해 간단히 만들 수 있다.

direction이 R인 경우 현재 위치에서 한 칸 오른쪽으로 갔을 때 length와 같은지 비교해준다. (전역 변수로 선언했기 때문에 인수로 전달할 필요가 없다.)

또한, 인수로 전달받은 map에서 오른쪽으로 한 칸 이동한 곳의 부울 값을 읽어, true면 이동할 수 없고, false면 이동할 수 있도록 한다.

direction이 ‘D’, ‘L’, ‘U’인 경우에도 동일하게 처리해주면 된다.

이제 해당 행의 끝에 달하거나 이미 지나온 땅을 다시 밟을 위기에 처했을 때, 이동할 수 있는지 없는지 사전에 알 수 있다.

그럼 Movable()이 false를 반환하면, 방향을 틀어준 뒤 앞으로 나아가면 된다.

public static void Turn()

{

switch (direction)

{

case ‘R’ :

direction = ‘D’;

break;

…

}

}

public static void Move()

{

switch (direction)

{

case ‘R’ :

pos[1]++;

break;

…

}

}

이렇게 Turn()과 Move()함수도 switch문을 사용해 간단히 만들 수 있을 것이다.

for루프를 빠져나온 뒤, snailed배열은 그대로 반환할 수 있도록 모든 준비가 끝난 상태이다.

이대로 제출하면 실행 시간은 약 3초정도 걸린다.

Solutions:

Solutions 채널에서는 다른 사람들과 자신의 코드를 공유할 수 있는 기능을 제공한다.

물론 코드를 직접 해결하면서도 많은 것을 배울 수 있지만, 다른 사람의 코드를 검토해보는 것도 정말 중요하다. (사실상 Codewars를 이용하는 가장 큰 이유…)

다른 사람들의 풀이와 자신의 풀이를 비교해본 뒤, 자신의 스파게티 코드와는 전혀 다른 아이큐 250 저세상 풀이를 보고 감탄을 금치 못한 사람들이 해당 코드를 추천할 수도 있다.

풀이가 기막히게 참신하면 Clever추를,

효율성과 가독성을 모두 잡은 입사 테스트 전용 코드에는 Best Practices추를 박는다.

Snail Kata의 풀이 중 Best Practices와 Clever을 독점한 dlcoe의풀이를 한번 보도록 하자.

public static int[] Snail(int[][] array)    

{

        int l = array[0].Length;

        int[] sorted = new int[l * l];

        Snail(array, -1, 0, 1, 0, l, 0, sorted);

        return sorted;

    }

public static void Snail(int[][] array, int x, int y, int dx, int dy, int l, int i, int[] sorted)

{

        if (l == 0)

            return;

        for (int j = 0; j < l; j++)

        {

            x += dx;

            y += dy;

            sorted[i++] = array[y][x];

        }

        Snail(array, x, y, -dy, dx, dy == 0 ? l - 1 : l, i, sorted);

}

놀랍게도 이게 코드의 전부이다.

한 줄 한 줄 뜯어보면,

먼저 array의 길이를 구한 후, 반환해야 하는 배열의 크기에 맞는 int[]를 선언한다.

여기까지는 똑같지만, recursive를 사용해 아주 간결하게 풀어냈다.

(여기서 잠깐!) Recursive란?

재귀 함수 라고도 하는데, 위 팩토리얼을 계산하는 것과 같이, 함수가 자기 자신을 호출하는 형태를 말한다.

모르는 사람 없지만 아무튼

Snail()함수에 array와 int x, y(각각 pos[0]과 pos[1]에 상응한다.), 그리고 int dx, dy, 길이를 나타내는 l과 sorted[]의 인덱스 위치를 지정하는 i, 마지막으로 배열 sorted를 전달한다.

Snail()함수에 들어서면 if (l == 0) return;을 통해 empty matrix를 잡아낸다.

이후 ,

for (int j = 0; j < l; j++) 에서는 x += dx;와 y += dy;를 통해 한칸 한칸 이동하며 sorted를 채운다.

여기에서 전달받은 dx와 dy는 각각 1과 0으로, 처음 이 함수가 호출되었을 때에는 오른쪽으로만 움직인다. 이 다음이 핵심이다.

Snail(array, x, y, -dy, dx, dy == 0 ? l - 1 : l, i, sorted);

이 코드의 천재성을 엿볼 수 있는 부분이다.

전달받았던 dx와 dy를 서로 교차시켜 dx의 자리에 -dy를, dy의 자리에 dx를 전달한다.

다시 한번 호출된 Snail함수는 이번엔 dx가 0이고, dy가 -1이기 때문에 밑으로만 움직인다.

int l은 for문의 반복 횟수를 정하는데, dy == 0, 즉, 오른쪽 또는 왼쪽으로 움직이다가 이 함수를 호출하면 l - 1을 통해 반복 횟수를 조절하며 필자의 해법의 Movable()함수를 대신한다. 아주 간단한 삼항 조건 연산자로 말이다.

이렇게 l == 0이 되면 아까 empty matrix를 걸러냈던 조건문에 걸리며 그대로 반환된다.

Snail Kata는 4급난이도가 아닌것은 아니지만 다른 Kata에 비하면 비교적 쉽다. 직관적인 해법이 와닿고, 그 해법도 구현하기 쉬워서 다소 쉽게 느껴진다.

https://www.codewars.com/kata/5c2fd9188e358f301f5f7a7b

Bird Mountain - the river도 4급인 것을 보면 Snail이 확실히 쉬운 편은 맞다. (근데 저건 진심 왜 3급이 아닌지 모르겠음)

하지만 그렇다고 dlcoe가 다른 방법을 쓴 것은 아니다. 같은 방법을 recursive를 사용해 다르게 구현했을 뿐.

결론: 재귀함수를 애용합시다.