문제

정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

입력

n : 4

출력

[1,2,9,3,10,8,4,5,6,7]

제한사항

n은 1 이상 1,000 이하입니다.

내가 했던 풀이 방법

1. snail 배열을 달팽이의 형태로 선언한다. index번째 배열은 index+1 크기의 배열로 초기화된다.
2. 1부터 n까지의 누적 합을 계산해 sum에 저장한다. (해당 내용은 달팽이가 다 채워짐을 의도한다. 후에 달팽이 채우기에서 조건식을 이용해 더이상 이동할 수 없을 경우 break해도 되지만, 시간 초과가 안 나므로 더 간단한 방법으로 구현했다.)
3. 초기 direction은 아래로 향하는 방향이므로 down으로 초기화해주고, num을 1로 초기화해준다. num은 채워진 순서를 의미한다.
4. current는 [0, 0]으로 해당 위치부터 달팽이 채우기가 시작된다.
5. snail의 current 위치에 num을 저장해준다. 현재 direction에 따라 다르게 동작한다. down일 경우, current[0]을 1 증가시켜준다. [0, 0]에서 아래 방향으로 간다면 [1, 0], [2, 0] 순으로 가기 때문이다. 만약 증가될 current 값이 index를 벗어나거나, 해당 위치에 이미 달팽이가 채워져있다면, 방향을 right로 바꿔주고 current[0]을 1 증가시키는 것이 아닌 current[1]을 1 증가시켜준다. [4, 0]에서 더 아래로 갈 수 없다면 [4, 1][4, 2] 순으로 가기 때문이다. up일 경우, current[0]와 current[1] 모두 1 감소시켜준다. [4, 4]에서 위로 이동한다면 [3, 3], [2, 2] 순으로 이동하기 때문이다. 이번에도 index를 벗어나거나 해당 위치에 달팽이가 채워져있다면, 방향을 down으로 바꿔주고 감소시키지 않고 current[0]을 1 증가시켜준다. 마지막으로 right일 경우 current[1]을 1 증가시켜준다. [4, 1]에서 [4, 2], [4, 3]으로 이동하기 때문이다. 이번에도 index를 벗어나거나 해당 위치에 달팽이가 채워져있다면 방향을 up으로 바꿔주고, current[0]과 current[1]을 1 감소시켜준다. 하나의 달팽이 채우기가 진행될 때마다 num은 1씩 증가된다. 이를 num이 sum 보다 커질 때까지 반복한다.
6. 만들어진 2차원 배열을 1차원으로 변환해준다.

코드

function solution(n) {
    var answer = [];
    let snail = Array.from({length: n}, (_, index)=>Array(index+1).fill(0));
    let sum = 0;
    for(let i=1; i<=n; i++) {
        sum+=i;
    }
    
    let direction = "down";
    let num = 1;
    let current = [0, 0];
    while(true) {
        if(num>sum) break;
        snail[current[0]][current[1]] = num;
        if(direction==="down") {
            if(current[0]+1>=n) {
                direction = "right";
                current[1]++;
            } else if(snail[current[0]+1][current[1]]!==0) {
                direction = "right";
                current[1]++;
            } else {
                current[0]++;
            }
        } else if(direction==="up") {
            if(current[0]-1<0) {
                direction = "down";
                current[0]++;
            } else if(snail[current[0]-1][current[1]-1]!==0) {
                direction = "down";
                current[0]++;
            } else {
                current[0]--;
                current[1]--;
            }
        } else {
            if(current[1]+1>=n) {
                direction = "up";
                current[0]--;
                current[1]--;
            } else if(snail[current[0]][current[1]+1]!==0) {
                direction = "up";
                current[0]--;
                current[1]--;
            } else current[1]++;
        }
        num++;
    }
    
    answer = snail.flat();
    return answer;
}

회고

딱 어제 운 좋게 백준 10157 자리배정 문제를 풀었다. 해당 문제보다 이 내용이 조금 더 복잡하기 때문에 프로그래머스 문제로 기록하고자 한다. 백준 문제는 직사각형이라 index 관리가 간단한데 달팽이 채우기는 삼각형이라 index를 조금 더 복잡하게 관리해주어야 하기 때문이다. 그래도 저 문제를 타이밍 좋게 푼 덕에 이번 문제는 수월하게 풀이했다.