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

문제 풀이1 - 2차원 배열에 값을 담기

해당 문제에서는 삼각형을 표현 해야하는데, 이는 n x n의 2차원 배열로 표현할 수 있습니다.

달팽이 형태를 채우는것은 2차원 배열에서 아래 → 오른쪽 → 왼쪽으로 진행하면서 값을 채워나가게 됩니다.

문제풀이 흐름

1. n x n 2차원 배열을 선언한다.
2. 현재 위치 (0,0) 에서부터 방향에 따라 이동할 수 없을 때까지 숫자를 채운다.
3. 아래로 이동 → 오른쪽으로 이동 → 왼쪽위로 이동
4. 채워진 숫자를 차례대로 1차원 배열에 옮겨서 반환한다.

1. n x n 2차원 배열 선언

int[][] triangle = new int[n][n];
int v = 1;

v변수는 채워넣은 값으로 1씩 증가할 값입니다.

2. 현재위치를 (0, 0)으로 초기화

int x = 0;
int y = 0;

3. 방향에 따라 이동할 수 없을때까지 숫자 채우기

while(true) {
    //아래

    //오른쪽

    //왼쪽위
}

1. 아래로 이동

   while (true) {
               triangle[y][x] = v++;
               if( y + 1 == n || triangle[y + 1][x] != 0) break;
               y += 1;
           }
   if (x + 1 == n || triangle[y][x + 1] != 0) break;
   x += 1;

2. 오른쪽으로 이동

   while (true) {
                   triangle[y][x] = v++;
                   if(triangle[y - 1][x - 1] != 0) break;
                   x -= 1;
                   y -= 1;
               }
               if (y + 1 == n || triangle[y + 1][x] != 0) break;
               y += 1;

3. 왼쪽위로 이동

   while (true) {
               triangle[y][x] = v++;
               if(triangle[y - 1][x - 1] != 0) break;
               x -= 1;
               y -= 1;
           }
           if (y + 1 == n || triangle[y + 1][x] != 0) break;
           y += 1;

4. 채워진 숫자를 1차원 배열에 옮겨 반환

int[] result = new int[v - 1];
int index = 0;
for(int i = 0; i < n; i++) {
   for (int j = 0; j <= i; j++) {
       result[index++] = triangle[i][j];
       }
   }

전체코드

class Solution {
    public int[] solution(int n) {
        int[][] triangle = new int[n][n];
        int v = 1;
        int x = 0;
        int y = 0;

        while(true) {

            //아래
            while (true) {
                triangle[y][x] = v++;
                if( y + 1 == n || triangle[y + 1][x] != 0) break;
                y += 1;
            }
            if (x + 1 == n || triangle[y][x + 1] != 0) break;
            x += 1;

            //오른쪽
            while (true) {
                triangle[y][x] = v++;
                if (x + 1 == n || triangle[y][x + 1] != 0) break;
                x += 1;
            }
            if (triangle[y - 1][x - 1] != 0) break;
            x -= 1;
            y -= 1;
            //왼쪽위
            while (true) {
                triangle[y][x] = v++;
                if(triangle[y - 1][x - 1] != 0) break;
                x -= 1;
                y -= 1;
            }
            if (y + 1 == n || triangle[y + 1][x] != 0) break;
            y += 1;

        }
        int[] result = new int[v - 1];
            int index = 0;
            for(int i = 0; i < n; i++) {
                for (int j = 0; j <= i; j++) {
                    result[index++] = triangle[i][j];
                }
            }
        return result;
    }
}

문제풀이2 - dx, dy로 방향 정하기

dx와 dy는 x의 변화량과 y의 변화량을 의미합니다.

특정방향으로 이동할때, 해당 좌표값이 어떻게 변화하는지에 대한것을 중심으로 알아봅시다.

특정 좌표 (x, y) 가 있을 때, 상하좌우의 움직임에 따른 좌표의 변화량은 다음과 같습니다.

	상	하	좌	우
dx	0	0	-1	1
dy	-1	1	0	0

해당 값을 배열에 담아서 dx, dy 변수를 생성해 줍니다.

private static final int[] dx = {0, 0, -1, 1};
private static final int[] dy = {-1, 1, 0, 0};

이동에 따른 값의 변화량을 배열에 옮겻으니 해당 배열의 인덱스가 방향이 됩니다.

인덱스 0은 상, 1은 하, 2는 좌, 3은 우 방향이 되지요.

1. 변화량 상수 생성

해당 문제에서는 3개의 방향을 사용합니다. 아래, 오른쪽 왼쪽 위

	아래	오른쪽	왼쪽 위
dx	0	1	-1
dy	1	0	-1

이를 배열에 담아서 변수로 나타내 봅시다.

private static final int[] dx = {0, 1, -1};
private static final int[] dy = {1, 0, -1};

2. 방향 변수 생성

int x = 0; //x좌표
int y = 0; //y좌표
int d = 0; //방향 변수

3. 배열에 값 넣기

int[][] triangle = new int[n][n];
int v = 1;
   while (true) {
      triangle[y][x] = v++;
      int nx = x + dx[d]; 
      int ny = y + dy[d];
      if (nx == n || ny == n || nx == -1 || ny == -1 || triangle[ny][nx] != 0) {
           d = (d + 1) % 3;
           nx = x + dx[d];
           ny = y + dy[d];
           if (nx == n || ny == n || nx == -1 || ny == -1 || triangle[ny][nx] != 0) break;
       }
  }

해당 코드에서는 d값에 따라서 다음 배열위치를 결정하게 됩니다.

int nx = x + dx[d]; 
int ny = y + dy[d];

배열위치를 결정한후, 더이상 진행할 수 없는 배열위치인 경우의 처리를 추가했습니다.

 if (nx == n || ny == n || nx == -1 || ny == -1 || triangle[ny][nx] != 0) {
}

nx == n || ny == n 은 아래와 오른쪽으로 이동하는 경우에 배열의 크기를 초과한 경우,

nx == -1 || ny == -1 은 왼쪽위로 이동하는 경우에 배열의 크기를 초과한 경우,

triangle[ny][nx] ≠ 0 은 이미 숫자가 써잇는 경우입니다.

만약 배열위치가 더이상 진행 되지 않는경우에,

d = (d + 1) % 3;
nx = x + dx[d];
ny = y + dy[d];

d = (d + 1) % 3; d의 값에 +1을 하여 방향을 바꾸었고, 2를 초과하는경우 다시 0으로 바꾸엇습니다.

방향을 바꾼후, nx = x + dx[d]; ny = y + dy[d]; 바뀐 방향에 따른 x와y의 변화값을 실행하였습니다.

전환된 방향으로도 진행을 못하는 경우 숫자채우기를 종료합니다.

if (nx == n || ny == n || nx == -1 || ny == -1 || triangle[ny][nx] != 0) break;
}

4. 현재 위치 업데이트

x = nx;
y = ny;

5. 1차원 배열로 값 리턴

int[] result = new int[v - 1];
            int index = 0;
            for(int i = 0; i < n; i++) {
                for (int j = 0; j <= i; j++) {
                    result[index++] = triangle[i][j];
                }
            }
        return result;

전체 코드

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    // 변화량 상수 생성
    private static final int[] dx = {0, 1, -1};
    private static final int[] dy = {1, 0, -1};
    public int[] solution(int n) {
        int x = 0;
        int y = 0;
        //방향 변수 생성
        int d = 0;

        int[][] triangle = new int[n][n];
        int v = 1;
        while (true) {
            triangle[y][x] = v++;
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx == n || ny == n || nx == -1 || ny == -1 || triangle[ny][nx] != 0) {
                d = (d + 1) % 3;
                nx = x + dx[d];
                ny = y + dy[d];
                if (nx == n || ny == n || nx == -1 || ny == -1 || triangle[ny][nx] != 0) break;
            }
            x = nx;
            y = ny;
        }

        int[] result = new int[v - 1];
        int index = 0;
        for(int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                result[index++] = triangle[i][j];
            }
        }
        return result;
    }

}