[프로그래머스] Level2 - 삼각 달팽이(Javascript)

프로그래머스

▶ 문제 요약

1. 정수 n이 매개변수로 주어진다. 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후

2. 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 만들어라.

 

▶ 정답 코드

function solution(n) {
    let answer = [];
    // n * n배열 만들고 0을 채우기
    let array = new Array(n).fill().map(() => new Array(n).fill(0));
    // 방향 설정(아래, 우측, 대각)
    const dx = [1, 0, -1], dy = [0, 1, -1];
    // 현재 위치를 표시할 변수
    let x = 0, y = 0; 
    
    // 총 채워야 하는 개수를 도달하기 위해 필요
    let num = 1;
    // 총 채워야 하는 개수
    let total = n * (n + 1) / 2;
    // 방향 전환을 위해 필요한 변수
    let direction = 0;
    
    // 채워야 하는 개수를 도달할 때까지
    while (num <= total) {
    	// 현재 방향이 범위를 벗어나지 않거나 숫자가 채워져 있지 않은경우
        if (x >= 0 && x < n && y >= 0 && y < n && array[x][y] === 0) {
           // 현재 숫자 넣어주기
           array[x][y] = num;
           // 다음 숫자를 위해서 늘리기
           num ++;
        // 만약 범위 벗어났다면 다음 방향을 위해
        // 이전 위치로 돌려놔야한다.
        } else {
           x -= dx[direction];
           y -= dy[direction];
           direction = (direction + 1) % 3;
        }
 		
        // 현재 위치를 계속 업데이트한다.
        x += dx[direction];
        y += dy[direction];
    }
    
    // 이중 for문을 도는데 값이 있는곳까지만 돈다.
    for (let i = 0; i < n; i++) {
        for (let j = 0; j <= i; j++) {
            // 배열 추가
            answer.push(array[i][j]);
        }
    }
	
    return answer;


}

▶ 풀이 과정

1. n * n을 배열을 만들고 0을 채운다. 값을 채워나가기 위함이고 나중에 방문했는지 확인도 가능하다.

 

2. 방향 정보를 담는다. 우리가 돌아야할 방향은 3가지 방향이다. x, y 축 고려해서 아래[1,0], 우측[0,1] , 대각선[-1,-1] 방향이다. 

 

3. 조건문 세우는게 중요한데 우리는 총 채워야 하는 개수를 구해서 채워질 때까지 돌아야지 문제가 해결된다. 식은 n * (n + 1) / 2이다.

 

4. while문을 이용해서 총 채워야 하는 개수에 도달할 때까지 돌아준다.

 

5. 만약 현재 위치(x,y)가 배열의 범위를 벗어나지 않았거나 array배열에 숫자가 채워지지 않았다면 배열의 현재 위치에 숫자를 넣어주고 다음 배열에 숫자를 넣기 위해서 숫자를 증가시킨다.

 

6. 만약 현재 위치(x,y)가 배열의 범위를 벗어나거나 array배열에 숫자가 채워져 있다면 범위를 벗어나게 되면 다음 위치를 탐색하기 어려우므로 이전 위치로 돌아가준다.

예를 들어 n = 4라면 배열의 인덱스상 3까지만 값이 존재한다. 근데 현재 위치가 (3, 4)라면? 범위를 벗어난다 그 상태에서 다음 방향을 순회하면 범위가 계속 벗어날 수밖에 없으므로 이전 위치로 돌려놔야한다. 

아래 방향을 더 이상 못 가면 우측 방향을 가야한다. 주어진 방향 정보를 계속 순회해야한다. 그래서 현재 방향을 주어진 방향 정보 안에서 바꿔줘야 하므로 (direction + 1) % 3 이렇게하면 계속 순회한다.

 

7. 현재 위치(x, y)를 방향 정보에 맞추어 계속 업데이트 한다.

 

8. 최종적으로 array가 다 채워졌으면 이제 새로운 배열에 옮겨 담아야한다. 이중 For문을 사용하는데 우리는 값이 채워진 부분만 보고 싶다. 예를 들어 n = 4인 경우 [[1, 0, 0, 0], [2, 9, 0, 0], [3, 10, 8, 0], [4, 5, 6, 7]] 이렇게 배열이 채워진다. 근데 여기서 열을 순회하는 부분(이중 for문에서 두 번째 부분)을 i의 크기만큼만 돌면 0의 값은 안 들어가게 되서 최종적으로 우리가 원하는 값을 구할 수 있다.