🎯문제
정수 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] |
✏️풀이
코드
class Solution {
public int[] solution(int n) {
// 등차수열의 합 공식을 사용하여 배열 크기 설정
int[] answer = new int[n*(n+1) / 2];
// 직접 값을 대입하기 위한 2차원 배열 생성
int[][] matrix = new int[n][n];
// x, y 좌표, 배열에 들어갈 값이 되는 변수 선언
// 이때 시작부터 x좌표가 1 증가하므로 x는 -1로 초기화
int x = -1, y = 0, value = 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] = value++;
}
}
int index = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
// 해당 배열에 값이 0일 경우 반복문 종료
if(matrix[i][j] == 0) {
break;
}
answer[index++] = matrix[i][j];
}
}
return answer;
}
}설명
배열의 인덱스를 잘 움직여서 값을 대입하는 문제이다. 문제에서 나온 그림을 조금 더 이해하기 쉽도록 2차원 배열로 바꾸어서 생각했다.
2차원 배열로 바꿔어서 생각하는 방법은 쉽다. 하나의 예시로 그림의 가장 왼쪽에 있는 삼각형을 가지고 바꿔보도록하겠다.
| 1 | |||
|---|---|---|---|
| 2 | 9 | ||
| 3 | 10 | 8 | |
| 4 | 5 | 6 | 7 |
이런 식으로 왼쪽으로 밀어서 생각을 하면 된다. 이때 아래로 먼저 값을 채우고 우측으로 가면서 값을 채운 뒤 좌측 대각선 위쪽으로 올라가면서 값을 채운다. 이 행위를 값이 다 채워질 때까지 반복하면 된다.
위의 코드에서 x = -1로 선언을 했는데 그 이유는 조건문에서 i % 3 == 0일때가 성립하게 된다. 이때 x++가 되는데 x = 0으로 선언을 할 경우 배열의 값이 [0][0]이 아닌 [1][0]부터 값이 채워지기 때문이다.
2차원 배열에 값을 다 저장한 뒤 1차원 배열에 값을 옮겨담는다. 이때 2차원 배열에서 값이 0일 경우는 그 뒤는 더이상 탐색할 필요가 없으므로 바로 반복문을 종료시킨 뒤 다음 행으로 넘어간다.
💡느낀 점
처음 문제를 봤을 때 어떠한 규칙이 있지 않을까 생각하면서 문제를 계속 보게 되었다. 그러다가 결국 배열의 인덱스를 조절하는 방법으로 풀었는데, 아직 실력이 부족하면서 효율성을 높여보겠다고 생각하다가 벌받은 것 같다. 처음부터 완벽한 코드를 짜는 것이 아닌 생각나는 것을 바로 도전해보는 습관부터 들여야겠다.
링크
