프로그래머스 - 삼각 달팽이

프로그래머스 - 삼각 달팽이

https://programmers.co.kr/learn/courses/30/lessons/68645

2021/04/14

문제 접근 방법

list의 길이가 1부터 하나씩 증가하는 형태로 n개의 list를 생성한다.
1부터 가장 큰 수까지 방향에 맞게 list에 넣는다.

가장 큰 수

가장 큰 수는 n이 1, 2, 3, 4, 5, 6 일 때 1, 3, 6, 10, 15, 21 과 같이
[초항이 1이며 [초항이 2이고 공차가 1인 '등차수열']을 계차로 갖는 '계차수열']의 n번째 항임을 알 수 있다.

Layer class를 만든다.

Array를 상속받아 Layer라는 클래스를 만든다.
삼각 달팽이의 각 층을 구성하게 할 것이다.
아래와 같은 기능이 필요하다.

1. 가장 앞에서부터 비어있는(empty)곳에 삽입
2. 가장 뒤에서부터 비어있는(empty)곳에 삽입

Triangle class를 만든다.

Layer들이 n개 쌓여있는 삼각 달팽이 이다.
아래와 같은 기능이 필요하다.

1. 길이가 1부터 1씩 증가하는 n개의 Layer생성
2. 입력받은 정수 n에 대한 최대값 구하기
3. 채우는 방향에 맞춰 최대값까지 채우기
4. 하나의 Array로 돌려주기

완성한 solution

// list의 첫번째 값이 1부터 하나씩 증가하는 형태로 n개의 list를 생성한다
// 1부터 가장 큰 수까지 방향에 맞게 list에 넣는다.
// 가장 큰 수는 n이 1, 2, 3, 4, 5, 6 일 때 1, 3, 6, 10, 15, 21 과 같이
// [초항이 1이며 [초항이 2이고 공차가 1인 '등차수열']을 계차로 갖는 '계차수열']의 n번째 항임을 알 수 있다.


class Layer extends Array { // 삼각 달팽이의 각 층
    constructor(n) {
        if (!Number.isInteger(n)) {
            throw SyntaxError(`argument must be 'Number'`);
        }
        super(n);
        this.front = 0, this.back = this.length - 1;
    }

    frontInsert(...arg) { // 앞에서부터 빈곳(empty)에 삽입
        for (let i = 0; i < arg.length; i++) {
            this[this.front + i] = arg[i];
        }
        this.front += arg.length;
    }
    backInsert(...arg) { // 뒤에서부터 빈곳(empty)에 삽입
        for (let i = 0; i < arg.length; i++) {
            this[this.back - i] = arg[arg.length - i - 1];
        }
        this.back -= arg.length;
    }
}

class Triangle { // 삼각 달팽이
    constructor(n) {
        this.n = n;
        this.maxNum = this.maximum(n);
        this.init();
        this.fill();
    }

    init() { // 각 층 생성
        for (let i = 0; i < this.n; i++) {
            this[i] = new Layer(i + 1);
        }
    }

    direction() { // 클로저 패턴
        let fn = {}, count = 0, now = this.n, floor = 0;
        // 채워 나갈 방향에 맞는 함수
        fn.down = (num) => {
            this[floor].frontInsert(num);
            floor += 1;
        }
        fn.right = (num) => {
            this[floor].frontInsert(num);
        }
        fn.up = (num) => {
            this[floor].backInsert(num);
            floor -= 1;
        }
        fn.run = ['down', 'right', 'up'];

        return (num) => { // 방향을 정하고 실행
            now -= 1;
            if (!now) {
                count += 1;
                now = this.n - count;
            }
            fn[fn.run[count % 3]](num);
        }

    }

    fill() { // maxNum까지의 숫자를 채움
        let j = this.direction();
        for (let i = 1; i <= this.maxNum; i++) {
            j(i);
        }
    }

    maximum(n) { // [초항이 1이며 [초항이 2이고 공차가 1인 '등차수열']을 계차로 갖는 '계차수열']의 n번째 항
        return ((n + 2) / 2) * (n - 1) + 1
    }

    report() { // 하나의 Array로 돌려줌(result)
        let temp = [];
        for (let i = 0; i < this.n; i++) {
            for (let j of this[i]) {
                temp.push(j);
            }
        }
        return temp;
    }
}

function solution(n) {
    let temp = new Triangle(n);
    return temp.report();
}

maxNum을 구하는 방법

위에서 언급한 것처럼 계차수열의 n번째 항을 구하는 방법으로 도출했다.
등차수열을 계차로 같은 계차수열의 경우
초항 + n번째 항 까지 계차의 합 이라고 할 수 있고,
그 계차가 등차수열이니 등차수열의 합을 구하려면
등차수열의 길이 * 평균 이 될것이다.

공차가 1이고 초항이 2 이므로
(n + 2) / 2 * (n - 1) 이 계차수열의 n번째 항까지 계차의 합이 된다.
여기에 계차수열의 초항(1)을 더해주면 계차수열의 n번째 항이 되는것이다.

• '등차수열의 평균은 (처음 + 끝) / 2 이다.'

방향에 맞게 채우기

방향은 3가지로 나뉜다.
내려오는 방향, 오른쪽 방향, 올라가는 방향.

처음에는 (col, row)를 변수로 두고 위치를 구할까 했지만,
방향의 패턴을 이용하기로 하였다.

1. 방향전환의 순서는 아래를 반복한다.
   1. 내려오는 방향
   2. 오른쪽 방향
   3. 올라가는 방향
2. 내려오는 방향부터 시작한다.
3. n번만큼 이동하면 다음방향으로 전환된다.
4. 방향전환이 이뤄지면 그 다음 방향전환까지 이동거리가 1 감소한다.
   • 즉 오른쪽으로 n - 1번 이동후 방향전환,위쪽으로 n - 2번 이동후 방향전환 ...(끝날 때까지)

위와 같은 형태로 삽입되는 수와 관계없이 실행되는 순서를 방향으로 잡고,
1부터 maxNum까지 숫자를 삽입해주기만 한다.

하나의 Array로 만들기

처음에는 Triangle도 Array를 상속하게 한뒤
각 Layer를 반복가능하게 하여 flat 시키려고 하였지만
callStack이 넘치는 바람에 for문을 사용하였다.

아쉬웠던 점

일단 수학적 능력이 아쉬웠다.
접근 방법을 떠올려도 수식이 떠오르지 않았다.
(물론 검색하면 된다. 하지만 코드로 표현하기 위해 이해해야 한다. - 라이브러리를 쓰는게 아니라면...)

또 하나는 다양하게 바라보는 관점이었다.
maxNum을 만들 때 사용된 수식이 아무리 봐도 깔끔하지 않아,
전개를 해보니 (n * (n + 1)) / 2 과 같은 수식이 되었다.
...

어디서 많이 봤다 했는데 1부터 n까지의 합이다.

n에 대한 최대값을 확인할 때 조금 더 다양하게 바라보지 못한게 아쉬웠다.
(만약 바로 눈치 챘다면 훨씬 빠르게 완료했을 것 같다.)

다양하게 바라보자

물론 말이야 쉽지 한다고 다 되는 것은 아닐 것이다.
그래도 노력은 해보자.