https://programmers.co.kr/learn/courses/30/lessons/68645
문제 설명
- 정수 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] |
풀이 방법
삼각형이 아닌 n*n 매트릭스를 만들어 숫자들을 왼쪽으로 정렬하여 생각한다.
입출력 예시 1을 보면 다음과 같다.
1 | |||
2 | 9 | ||
3 | 10 | 8 | |
4 | 5 | 6 | 7 |
왼쪽 아래로 1씩 증가 -> 오른쪽으로 1씩 증가 -> 왼쪽 위 대각선으로 1씩 증가를 반복해주면 된다.
- matrix : 삼각 달팽이를 나타낼 n*n 배열
- i : 행을 나타내는 인덱스
- j : 열을 나타내는 인덱스
- k : 숫자를 나타내는 변수
1. answer의 크기는 n! 이므로 n*(n+1)/2이다.
2. n*n 배열을 생성하여 0으로 초기화한다.
3. 필요한 변수를 초기화하고 k가 answer의 크기일 때까지 반복한다.
- i+1이 0보다 작고 matrix [i+1][j] 배열의 값이 0일 때 matrix [++i][j]의 값에 ++k
- j+1이 0보다 작고 matrix[i][j+1] 배열의 값이 0일 때 matrix [i][++j]의 값에 ++k
- i가 0보다 크고 왼쪽 위 대각선 배열의 값이 0일 때 matrix [--i][--j]의 값에 ++k
4. matrix 값을 answer 배열에 담아 반환한다.
전체 코드
class Solution {
public int[] solution(int n) {
int[] answer = {};
answer = new int[n*(n+1)/2];
int[][] matrix = new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
matrix[i][j]=0;
}
}
int i=0,j=0,k=1;
matrix[0][0]=1;
while(k<answer.length){
//왼쪽 대각선
while(i+1<n&&matrix[i+1][j]==0){
matrix[++i][j]=++k;
}
//맨 밑
while(j+1<n&&matrix[i][j+1]==0){
matrix[i][++j]=++k;
}
//오른쪽 대각선
while(i>0&&matrix[i-1][j-1]==0){
matrix[--i][--j]=++k;
}
}
k=0;
for(i=0;i<n;i++){
for(j=0;j<=i;j++){
answer[k++]=matrix[i][j];
}
}
return answer;
}
}
다른 풀이
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 자바] 프로그래머스 > Lv.2 전화번호 목록 (0) | 2022.03.06 |
---|---|
[Java 자바] 프로그래머스 > Lv.2 가장 큰 수 (0) | 2022.03.04 |
[Java 자바] 프로그래머스 > Lv.2 기능 개발 (0) | 2022.03.02 |
[Java 자바] 프로그래머스 > Lv.2 큰 수 만들기 (0) | 2022.02.28 |
[Java 자바] 프로그래머스 > Lv.2 124 나라의 숫자 (0) | 2022.02.28 |
댓글