[68645] 삼각 달팽이

✔ 삼각 달팽이

[프로그래머스 68645]

문제 분석하기

삼각 달팽이의 갯수는 n+(n - 1)+...+1이므로 n*(n+1)/2

이때 삼각 달팽이를 왼쪽으로 밀어서 생각할 경우, 아래-오른쪽-위 대각선의 순서로 반복하며 채워지도록 함

 

예) n = 4

(0, 0), (0, 1), (0, 2), (0, 3) : 아래 (i가 0이면서 j가 0 ~ n일 동안 아래 방향 패턴을 유지)

(1, 1), (1, 2), (1, 3) : 오른쪽 (i가 1이면서 j가 1 ~ n일 동안 오른쪽 방향 패턴을 유지)

(2, 2), (2, 3) : 위 대각선 (i가 2이면서 j가 2 ~ n일 동안 위 대각선 방향 패턴을 유지)

(3, 3) : 아래 (i가 3이면서 j가 3 ~ n일 동안 아래 방향 패턴을 유지)

1
2	9
3	10	8
4	5	6	7

손으로 풀어보기

1. 삼각 달팽이가 움직이는 방향인 아래-오른쪽-대각선의 순서로 반복하며 2차원 배열에 저장
   • 아래 : x 증가
   • 오른쪽 : y 증가
   • 위 대각선 : x, y 감소
   • 이때 3개의 동작이 있으므로 나머지가 0일 동안에는 아래, 1일 동안에는 오른쪽, 2일 동안에는 위 대각선으로의 이동
2. 삼각 달팽이의 개수를 구해 1차원 배열을 생성
   • n*(n+1)/2
3. 2차원 배열의 값을 1차원에 저장

슈도코드 작성하기

n(밑변의 길이와 높이)
answer(밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열)
map(달팽이 채우기를 진행하는 2차원 배열)
x, y(달팽이 채우기 좌표)
number(달팽이 채우기 숫자)
for(i -> 0부터 n만큼) {
    for(j -> i부터 n만큼) {
        if(i % 3 == 0)
            아래로 내려가므로 x 증가
        else if(i % 3 == 1)
            오른쪽으로 가므로 y 증가
        else {
            대각선 위로 가므로 x, y 감소
        }
        map[x][y]에 number 저장 후 number 증가
    }
}
index(answer의 위치 인덱스)
for(i -> n만큼) {
    for(j -> n만큼) {
        if(map[i][j]가 0이라면)
            break;
        answer[index++]에 map[i][j] 저장
    }
}
answer 반환

코드 구현하기

/**
 * 68645) 삼각_달팽이
 */
public class L059_68645 {
    // n(밑변의 길이와 높이)
    public int[] solution(int n) {
        // map(달팽이 채우기를 진행하는 2차원 배열)
        int[][] map = new int[n][n];
        // x, y(달팽이 채우기 좌표)
        int x = -1, y = 0;
        // number(달팽이 채우기 숫자)
        int number = 1;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i % 3 == 0)
                    // 아래로 내려가므로 x 증가
                    x++;
                else if (i % 3 == 1)
                    // 오른쪽으로 가므로 y 증가
                    y++;
                else {
                    // 대각선 위로 가므로 x, y 감소
                    x--;
                    y--;
                }
                // map[x][y]에 number 저장 후 number 증가
                map[x][y] = number++;
            }
        }
        // answer(밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후,
        // 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열)
        int[] answer = new int[n * (n + 1) / 2];
        // index(answer의 위치 인덱스)
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 0)
                    break;
                // answer[index++]에 map[i][j] 저장
                answer[index++] = map[i][j];
            }
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L059_68645 solution = new L059_68645();

        int n = 4;

        int[] result = solution.solution(n);

        System.out.println(Arrays.toString(result));
    }
}