[구현 / Kotlin] 2022 SK ICT Family 개발자 채용 챌린지 - 2번

우선 간만에 알고리즘 문제를 접했던 터라 많이 어려웠다. FE / APP 개발 직군을 선택했고 총 4문제가 나왔는데 DP 1, 구현 1, 그래프 2 이렇게 나왔다. 사정이 있어서 30분 정도 뒤늦게 참석했고 2시간 동안 2번 하나만 풀었다. 시간이 더 있었어도 다른 문제를 풀지 못했을 것이다. 안드로이드 공부 때문에 알고리즘을 소홀히 했는데 앞으로는 편식하지 말고 알고리즘도 꾸준히 풀어야겠다.

문제

문제 저작권에 의해서 캡쳐는 하지 못했고 간단하게 설명하자면 주어진 배열을 재정렬하는 문제였다. 시계 방향, 반시계 방향으로 총 2가지의 방향이 있었으며 배열의 크기는 홀수와 짝수가 존재했다. 결과적으로 총 4가지 경우 대해 배열을 재정렬하는 문제였다.

풀이 언어

Kotlin

코드

class Solution {
    fun solution(n: Int, clockwise: Boolean, result: Array<Array<Int>>) {
        when (n % 2) {
            0 -> // 배열의 크기가 짝수
                if (clockwise) { // 시계 방향
                    move(n, 1, 1, listOf(0, 0), result)
                } else { // 반시계 방향
                    move(n, 1, -1, listOf(0, n - 1), result)
                }
            1 -> // 배열의 크기가 홀수
                if (clockwise) { // 시계 방향
                    move(n, 2, 1, listOf(0, 0), result)
                } else { // 반시계 방향
                    move(n, 2, -1, listOf(0, n - 1), result)
                }
        }
    }

    fun move(n: Int, finish: Int, direction: Int, src: List<Int>, result: Array<Array<Int>>) {
        // 우선 시계방향 기준으로 (1, 0) -> (0, 1) -> (-1, 0) -> (0, -1)
        val dx = listOf(1 * direction, 0, -1 * direction, 0)
        val dy = listOf(0, 1, 0, -1)

        // 인자로 받은 시작 지점의 좌표
        var x = src[1]
        var y = src[0]

        // 탐색 간격 (꺾이기 전까지의 간격이랄까?)
        var interval = n - 1

        // interval 을 저장하기 위한 임시 변수
        var temp = 0

        // 인자로 받은 최종 탐색 간격까지 탐색
        while (interval >= finish) {
            var cnt = 1 + temp

            // 모든 방향을 탐색
            for (i in 0..3) {
                // 진행 방향 (위에서 선언한 방향 배열을 활용)
                val nx = dx[i]
                val ny = dy[i]

                while (cnt <= temp + interval) {
                    // 좌표값 갱신
                    if (result[y][x] == 0) {
                        result[y][x] = cnt++
                    }
                    // 좌표 갱신
                    x += nx
                    y += ny
                    // 꺾이는 좌표에 도달한 경우 탐색 종료
                    if (cnt == temp + interval) {
                        result[y][x] = cnt
                        cnt = 1 + temp
                        x += nx
                        y += ny
                        break
                    }
                }
            }

            // 임시 변수 갱신
            temp += interval

            // 시계 방향인 경우 다음 시작 지점이 (0, 0) -> (1, 1) ... 이런 식으로 증가
            if (direction == 1) {
                x += 1
                y += 1
            } else { // 반시계 방향인 경우 다음 시작지점이 (0, n - 1) -> (1, n - 2) ... 이런 식으로 증가
                x -= 1
                y += 1
            }

            // 탐색 간격 갱신
            interval -= 2
        }

        if (n % 2 != 0) { // 배열의 크기가 홀수인 경우 가장 안쪽 1개만 갱신
            result[n / 2][n / 2] = temp + 1
        } else { // 배열의 크기가 짝수인 경우 가장 안쪽 4개 모두 갱신
            result[n / 2][n / 2] = temp
            result[n / 2 - 1][n / 2] = temp
            result[n / 2][n / 2 - 1] = temp
            result[n / 2 - 1][n / 2 - 1] = temp
        }
    }
}

풀이 방법

when (n % 2) {
    0 -> // 배열의 크기가 짝수
    if (clockwise) { // 시계 방향
        move(n, 1, 1, listOf(0, 0), result)
    } else { // 반시계 방향
        move(n, 1, -1, listOf(0, n - 1), result)
    }
    1 -> // 배열의 크기가 홀수
    if (clockwise) { // 시계 방향
        move(n, 2, 1, listOf(0, 0), result)
    } else { // 반시계 방향
        move(n, 2, -1, listOf(0, n - 1), result)
    }
}

우선 각 경우에 따라 나눠줬다. If-else 로 활용해도 되지만 최대한 Kotlin 스럽게 풀어보기 위해 When 을 활용했다. move 는 배열을 재정렬하는 함수이며, 매개변수는 앞에서부터 순서대로 배열의 크기, 탐색 간격, 탐색 방향, 시작 지점, 재정렬한 배열 이다.

// 우선 시계방향 기준으로 (1, 0) -> (0, 1) -> (-1, 0) -> (0, -1)
val dx = listOf(1 * direction, 0, -1 * direction, 0)
val dy = listOf(0, 1, 0, -1)

이후 방향을 지정해줬다.

시계 방향인 경우 (1, 0) -> (0, 1) -> (-1, 0) -> (0, -1), 반시계 방향인 경우 (-1, 0) -> (0, 1) -> (1, 0) -> (0, -1) 로 좌표이동을 한다.

// 인자로 받은 시작 지점의 좌표
var x = src[1]
var y = src[0]

// 탐색 간격 (꺾이기 전까지의 간격이랄까?)
var interval = n - 1

// interval 을 저장하기 위한 임시 변수
var temp = 0

// 인자로 받은 최종 탐색 간격까지 탐색
while (interval >= finish) {
    var cnt = 1 + temp

    // 모든 방향을 탐색
    for (i in 0..3) {
        // 진행 방향 (위에서 선언한 방향 배열을 활용)
        val nx = dx[i]
        val ny = dy[i]

        while (cnt <= temp + interval) {
            // 좌표값 갱신
            if (result[y][x] == 0) {
                result[y][x] = cnt++
            }
            // 좌표 갱신
            x += nx
            y += ny
            // 꺾이는 좌표에 도달한 경우 탐색 종료
            if (cnt == temp + interval) {
                result[y][x] = cnt
                cnt = 1 + temp
                x += nx
                y += ny
                break
            }
        }
    }

    // 임시 변수 갱신
    temp += interval

    // 시계 방향인 경우 다음 시작 지점이 (0, 0) -> (1, 1) ... 이런 식으로 증가
    if (direction == 1) {
        x += 1
        y += 1
    } else { // 반시계 방향인 경우 다음 시작지점이 (0, n - 1) -> (1, n - 2) ... 이런 식으로 증가
        x -= 1
        y += 1
    }

    // 탐색 간격 갱신
    interval -= 2
}

선언한 방향에 따라 탐색을 진행한다.

if (n % 2 != 0) { // 배열의 크기가 홀수인 경우 가장 안쪽 1개만 갱신
    result[n / 2][n / 2] = temp + 1
} else { // 배열의 크기가 짝수인 경우 가장 안쪽 4개 모두 갱신
    result[n / 2][n / 2] = temp
    result[n / 2 - 1][n / 2] = temp
    result[n / 2][n / 2 - 1] = temp
    result[n / 2 - 1][n / 2 - 1] = temp
}

배열의 가장 안쪽이 갱신되지 않는 오류가 있었다. 이 부분은 하드 코딩으로 해결했다.

결과

배열의 크기가 짝수이고 시계 방향

배열의 크기가 짝수이고 반시계 방향

배열의 크기가 홀수이고 시계 방향

배열의 크기가 홀수이고 반시계 방향