[프로그래머스] 정수를 나선형으로 배치하기

24년 12월 13일
해결한 문제 갯수: 24

 

문제 설명

 

문제 분석

- 주어진 크기 n x n의 2차원 배열에 1부터 n² 까지의 정수를 나선형으로 채우는 문제입니다. 숫자는 좌측 상단에서 시작하여 시계 방향으로 나선형을 그리며 채워집니다.

 

첫 번째 접근

function solution(n) {
    let d = 'right'
    let [i, j, value] = [0, 0, 1]
    
    const answer = Array.from({length: n}, () => new Array(n).fill(0))

    while(value <= n * n){
        answer[i][j] = value
        console.log(answer)

        if(d === 'right') {
            if(j + 1 < n && answer[i][j + 1] === 0) j += 1
            else {
                d = 'bottom'
                i += 1
            }
        } else if(d === 'bottom') {
            if(i + 1 < n && answer[i + 1][j] === 0) i += 1
            else {
                d = 'left'
                j -= 1
            }
        } else if(d === 'left') {
            if(j - 1 >= 0 && answer[i][j-1] === 0) j -= 1
            else {
                d = 'top'
                i -= 1
            }
        } else if(d === 'top') {
            if (i - 1 >= 0 && answer[i-1][j] === 0) i -= 1
            else {
                d = 'right'
                j += 1
            }
        }
        
        value += 1
    }
    
    return answer
}

 

1) 초기 설정 

- d: direction. 현재의 진행 방향

- i, j: 현재 위치하는 행과 열 인덱스

- value: 채울 숫자 값

2) 배열 생성

: Array.from()을 사용해, 각 행마다 새로운 배열을 생성합니다. (이는 참조복사 문제를 해결합니다.)

- 다음 코드방식은 주의해야 합니다. 이 방식은 동일한 배열의 참조를 복사하게 되어, 한 행의 값을 변경하면([0, 0]) 모든 행([1, 0], [2, 0]... or [0, 1], [0, 2])이 함께 변경되는 문제가 발생합니다.

new Array(n).fill(new Array(n).fill(0))

3) 방향 전환 로직

: 방향이 변경되는 순서는 'right - bottom - left - top'입니다.

: 각 방향('right', 'bottom', 'left', 'top')에 대해:

1. 다음 위치가 배열 범위 내에 있고 아직 채워지지 않았는지 확인
2. 조건을 만족하면 해당 방향으로 이동
3. 조건을 만족하지 않으면 다음 방향으로 전환

4) 상위 3명 선택

: 배열에서 상위 3명을 선택합니다.

 

두 번째 접근: 방향과 경계 조건 체크

function solution(n) {
    const directions = [
        [0, 1],  // right
        [1, 0],  // bottom
        [0, -1], // left
        [-1, 0]  // top
    ];
    
    const answer = Array.from({ length: n }, () => new Array(n).fill(0));
    
    const isValid = (x, y) => x >= 0 && x < n && y >= 0 && y < n && answer[x][y] === 0;
    
    let [x, y] = [0, 0];           // 현재 위치
    let directionIndex = 0;        // 현재 방향 인덱스
    
    // 1부터 n*n까지 숫자 채우기
    for (let i = 1; i <= n * n; i++) {
        answer[x][y] = i;
        
        // 다음 위치 계산
        let nextX = x + directions[directionIndex][0];
        let nextY = y + directions[directionIndex][1];
        
        // 다음 위치가 유효하지 않으면 방향 전환
        if (!isValid(nextX, nextY)) {
            directionIndex = (directionIndex + 1) % 4;
            nextX = x + directions[directionIndex][0];
            nextY = y + directions[directionIndex][1];
        }
        
        x = nextX;
        y = nextY;
    }
    
    return answer;
}

개선사항

- directions와 directionIndex를 사용해 index의 변경사항을 관리합니다.

- isValid 함수를 선언해, 인덱스값을 업데이트할 때 해당 값이 유효한지를 확인합니다. 

- 유효하지 않다면, 방향을 전환합니다.(directionIndex를 업데이트 합니다)