문제 설명
정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.
제한사항
•
n은 1 이상 1,000 이하입니다.
입출력 예
n | result |
4 | [1,2,9,3,10,8,4,5,6,7] |
5 | [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] |
6 | [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11] |
입출력 예 설명
입출력 예 #1
•
문제 예시와 같습니다.
입출력 예 #2
•
문제 예시와 같습니다.
입출력 예 #3
•
문제 예시와 같습니다.
나의 풀이
import java.util.*;
class Solution {
public int[] solution(int n) {
int[][] tri = new int[n + 1][];
for (int i = 1; i <= n; i++) {
tri[i] = new int[i];
}
tri[1][0] = 1;
int[][] direction = {
{1, 0}, //down
{ 0, 1}, //right
{-1, -1} //left_up
};
int row = 1;
int col = 0;
int fail = 0;
int dir = 0;
int num = 2;
while (fail < 3) {
int nRow = row + direction[dir][0];
int nCol = col + direction[dir][1];
if ( nRow < 0 || tri .length <= nRow
|| nCol < 0 || tri[row].length <= nCol
|| tri[nRow] == null
|| tri[nRow][nCol] != 0) {
dir = (dir + 1) % 3;
fail++;
continue;
} else {
fail = 0;
row = nRow;
col = nCol;
tri[row][col] = num++;
}
}
int[] answer = new int[n * (n + 1) / 2];
int index = 0;
for (int[] arr : tri) {
if (arr == null) continue;
for (int i = 0; i < arr.length; i++) {
answer[index++] = arr[i];
}
}
return answer;
}
}
Java
복사
Remark
•
풀이 아이디어
◦
배열의 크기와 row의 index를 맞추기 위해 tri[0]은 null로 놓음
◦
1, 0에서 시작
◦
방향 배열을 설정해서 다음 방향을 검사
▪
if 배열 범위를 벗어나거나/null이거나/0이 아니면 방향을 바꾼 후 실패 횟수 1 추가하고 방향 전환
▪
else 0이면 방향대로 한 칸 움직인 다음 배열에 숫자 표시
▪
방향 전환에 3번 실패하면 채우기가 마무리 된 것이므로 루프 종료
•
다른 분의 풀이
class Solution {
public int[] solution(int n) {
int[] answer = new int[(n*(n+1))/2];
int[][] matrix = new int[n][n];
int x = -1, y = 0;
int num = 1;
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
if (i % 3 == 0) {
++x;
} else if (i % 3 == 1) {
++y;
} else if (i % 3 == 2) {
--x;
--y;
}
matrix[x][y] = num++;
}
}
int k = 0;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
if(matrix[i][j] == 0) break;
answer[k++] = matrix[i][j];
}
}
return answer;
}
}
Java
복사
◦
진행 횟수가 n부터 시작해 1씩 작아지는 것을 이용한 멋있는 풀이
◦
맨 왼쪽 세로 n개를 채움 → 맨 아래 가로 n-1개를 채움 → 왼쪽 위로 n-2개를 채움 … 반복
