[프로그래머스] 삼각 달팽이

문제 설명

프로그래머스 레벨 2의 문제입니다. 월간 코드 챌린지 시즌1에 출제된 문제입니다.

 

 

위의 그림을 보면 쉽게 이해할 수 있는 문제입니다. 달팽이 배열이지만 삼각형의 구조를 가지고 있습니다.

 

 

 

삼각 달팽이 배열을 일차원 배열로 표현하여 반환하는 문제입니다.

 

풀이

def get_inc(x_inc, y_inc):
    if y_inc < 0 and x_inc < 0:
        return 0, 1
    elif y_inc > 0 and x_inc == 0:
        return 1, 0
    elif x_inc > 0 and y_inc == 0:
        return -1, -1


def solution(n):
    arr = []
    total_cnt = 0

    for i in range(n):
        arr.append([])
        for j in range(0, i + 1):
            total_cnt += 1
            arr[i].append(0)

    x = 0
    y = 0

    x_inc = 0
    y_inc = 1

    cnt = 1

    while True:
        arr[y][x] = cnt
        cnt += 1

        if cnt == total_cnt + 1:
            break

        if y + y_inc > len(arr) - 1:
            x_inc, y_inc = get_inc(x_inc, y_inc)
        elif x + x_inc > len(arr) - 1:
            x_inc, y_inc = get_inc(x_inc, y_inc)

        if arr[y + y_inc][x + x_inc] != 0:
            x_inc, y_inc = get_inc(x_inc, y_inc)

        y += y_inc
        x += x_inc

    result = []
    for item in arr:
        result.extend(item)

    return result

변수 설명

get_inc(x_inc, y_inc): get_inc는 x 증가 값, y 증가 값을 받아 x 증가 값과 y 증가 값을 계산해 반환하는 함수입니다.

x: 달팽이 배열의 x 값입니다.

y: 달팽이 배열의 y 값입니다.

x_inc: 달팽이 배열의 x증가 값입니다.

y_inc: 달팽이 배열의 y증가 값입니다.

cnt: 달팽이 배열에 들어갈 숫자 번호입니다.

total_cnt: n 달팽이 배열에 들어가 가장 큰 숫자입니다(n이 4라면 total_cnt는 10)

 

간단 설명

n이 4일 경우 달팽이 배열은 아래와 같은 이차원 배열과 같이 만들 수 있습니다.

 

 

정삼각형과 같이 생긴 구조를 직각 삼각형으로 수정하면 쉽게 배열의 구성을 생각해낼 수 있습니다.

[0], [0, 0], [0, 0, 0], [0, 0, 0, 0]

이런 2차원 배열을 모두 0으로 초기화시킨 후 while문을 돌립니다.

 

x, y의 값은 각각 0으로 초기화를 해줍니다. 다른 부분보다 가장 중요한 부분이 x_inc와 y_inc를 구하는 부분입니다.

x와 y의 증가는 아래와 같습니다

1. y값만 증가
2. x값만 증가
3. x와 y값 모두 감소

 

위의 세가지세 가지 경우가 있습니다. 그 이유는 오른쪽 직각 삼각형을 본다면 세 가지로만 화살표의 방향이 있습니다.

아래, 오른쪽, 왼쪽 위 이 세가지의 방향이 계속 반복합니다.

 

그렇기 때분에 y값 혹은 x 값이 배열의 길이보다 벗어나거나 이미 배열의 요소에 값이 들어가 있다면 현재의 x, y 증가 값을 통해 새로운 x, y 증가 값을 알아냅니다.