알아두면 쓸모있는 배열 회전

Introduction

코딩테스트를 준비하다보면 여러가지 구현 문제를 만나게 된다. 간단한 구현 문제는 요구사항을 보면서 바로 구현할 수 있지만, 대부분 그렇지 않다. 그래서 구현 문제를 잘 푸는 방법은 오로지 연습만이 살 길이다.

간단한 것 같으면서도 까다로운 구현이 배열을 회전하는 구현이다. 처음 배열을 돌리는 문제를 만나게 되면, 한번에 배열을 돌리고 싶어한다. 코딩의 천재라면 머릿 속에서 좌표가 모두 정리가 되어 한번에 돌리는 점화식이 딱 떠오를 수도 있다. 불행히도 나는 천재가 아니였고, 배열을 돌리는 문제를 만날 때마다 오래도록 고민했다.

그래서, 일반적인 배열을 돌리는 구현을 정리하기로 했다. 1차원 배열을 돌리는 것부터, 2차원 배열을 반전시키거나 회전시키는 배열까지 정리했다. 이것보다 복잡한 회전은 아래의 회전을 응용해서 만들 수 있을 것이라고 생각한다.

기본적이고 일반적인 배열 회전 구현을 알아보고, 필요할 때마다 가져다 쓰자.

1차원 배열의 회전

/*
    N = 배열의 크기
    A = 회전시킬 배열
    d = 왼쪽 혹은 오른쪽으로 회전
*/
void rotate(int N, int *A, int d)
{
    int B[N];
    copy(&A[0], &A[0] + N, &B[0]);

    for (int i = 0; i < N; i++)
        // d == 0 이면 왼쪽으로 회전 아니면 오른쪽으로 회전
        if (d == 0)
            A[i] = B[(i + 1) % N];
        else
            A[(i + 1) % N] = B[i];
}

2차원 배열 회전

반전

/*
    N: 행의 갯수
    M: 열의 갯수
    A: 2차원 배열
    d: 상하 혹은 좌우 반전
*/
void reverse(int N, int M, int **A, int d)
{
    int B[N][M];
    copy(&A[0][0], &A[0][0] + N * M, &B[0][0]);

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            // d == 0 이면 상하반전 아니면 좌우반전
            if (d == 0)
                A[i][j] = B[N - 1 - i][j];
            else
                A[i][j] = B[i][M - 1 - j];
}

Transpose(전치)

/*
    N: 행의 갯수
    M: 열의 갯수
    A: 2차원 배열
*/
void transpose(int &N, int &M, int **A)
{
    int B[N][M];
    copy(&A[0][0], &A[0][0] + N * M, &B[0][0]);

    swap(N, M);

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            A[i][j] = B[j][i];
}

여기까지는 쉽다. 외우지 않아도 그때그때 생각해서 풀 수 있는 수준

90도 회전

/*
    N: 행의 갯수
    M: 열의 갯수
    A: 2차원 배열
    d: 오른쪽으로 혹은 왼쪽으로 90도 회전
*/
void rotate(int &N, int &M, int **A, int d)
{
    int B[N][M];
    copy(&A[0][0], &A[0][0] + N * M, &B[0][0]);

    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            // d == 90 이면 오른쪽으로 90도 아니면 왼쪽으로 90도 회전
            if (d == 90)
                A[i][j] = B[N - 1 - j][i];
            else
                A[i][j] = B[j][M - 1 - i];
    
    swap(N, M);
}

배열을 4분할하여 회전하기

보통 배열의 행의 갯수와 열의 갯수가 같고, 갯수가 2의 제곱꼴 혹은 짝수로 주어진다. 일반적인 경우를 살펴보고, 응용이 필요하면 그때 그때 수정해서 사용하자.

/*
    N: 행의 갯수
    M: 열의 갯수
    A: 2차원 배열
    d: 오른쪽으로 혹은 왼쪽으로 회전
*/
void rotate(int N, int M, int **A, int d)
{
    int B[N][M];
    copy(&A[0][0], &A[0][0] + N * M, &B[0][0]);
    R = N / 2, C = M / 2;

    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            if (d == 1)
                A[i][j] = B[i + R][j];
            else
                A[i][j] = B[i][j + C];
    
    for (int i = 0; i < R; i++)
        for (int j = C; j < M; j++)
            if (d == 1)
                A[i][j] = B[i][j - C];
            else
                A[i][j] = B[i + R][j];
    
    for (int i = R; i < N; i++)
        for (int j = C; j < M; j++)
            if (d == 1)
                A[i][j] = B[i - R][j];
            else
                A[i][j] = B[i][j - C];
    
    for (int i = R; i < N; i++)
        for (int j = 0 ; j < C; j++)
            if (d == 1)
                A[i][j] = B[i][j + C];
            else
                A[i][j] = B[i - R][j];
}

번외편 배열 달팽이 순회

홀수 길이를 가진 정사각형 배열을 가운데부터 시작하여 밖으로 달팽이 집모양처럼 순회할 일이 가끔 있다. 당황하지 말고 기본적은 틀을 기억해두고 그때 그때 구현에 써먹자. 밖에서부터 안으로 들어가는 구현도 조금만 응용하면 쉽게 해결 가능하다.

/*
    N: 길이
    A: 2차원 배열
*/
void rotate(int N, int **A)
{
    int x = N / 2, y = N / 2;
    int dist = 0, dir = 0, k = 1, sw = -1;

    while (true)
    {
        dist += 1;

        for (int i = 0; i < dist; i++)
        {
            A[x][y] = k;
            y += sw, k += 1;
        }

        if (k >= N * N)
            break;
        
        dir = (dir + 1) % 4;
        
        for (int i = 0; i < dist; i++)
        {
            A[x][y] = k;
            x -= sw, k += 1;
        }

        dir = (dir + 1) % 4;
        sw *= -1;
    }
}