반응형
https://programmers.co.kr/learn/courses/30/lessons/68645
풀이
삼각 달팽이 문제는 규칙을 찾는것이 가장 어려웠다.
이 문제를 푸는데 가장 중요한 아이디어는
정삼각형 형태인 주어진 수들을 왼쪽으로 몰아 2차원배열에 직각삼각형 형태로 놓는다고 생각하는 것이다.
이렇게 생각을 바꾸고 나면 쉽게 풀이가 가능하게 된다.
- 적히는 숫자들의 총 갯수는 n*(n+1)/2 (등차수열의 합)이므로 answer배열의 크기를 n*(n+1)/2로 설정해 준다.
- 직각삼각형 형태로 수를 저장할 n*n의 2차원 배열을 하나 생성하고 여기에 해당하는 숫자들을 넣는 코드를 구현해야한다.
- 위의 그림에서 알 수 있듯이 1 ~ n*(n+1)/2의 수는 아래방향, 오른쪽방향, 위쪽대각선방향의 순서를 반복하며 적히게 된다.
- 이 때 방향이 달라질 때 마다 n개, n-1개, n-2개,...,1개의 수가 적히게 된다.
- 아래 방향 : r++ / 오른쪽 방향 : c++ / 대각선 위 방향 : r--, c--
- 위와 같이 적히는 좌표가 달라지게 되므로 적히는 수의 개수와 방향에 맞게 for문을 구현한다. (코드 참조)
- 방향이 달라질 때 마다 n을 1씩 감소시키고 n이 0이되면 수행을 종료한다.
- 2차원배열을 모두 채운 뒤에는 이를 1차원 배열인 answer에 해당하는 인덱스에 맞게 넣어줘야한다.
- 2차원배열을 왼쪽 위부터 차례로 탐색하며 0이 아닌 값이 담겨있는 경우만 answer에 넣어주면 된다.
class Solution {
public int[] solution(int n) {
int size = (n+1)*n/2;
int[] answer = new int[size];
int[][] temp = new int[n][n];
int num = 1;
int r = -1;
int c = 0;
size = n;
while(n>0){
//아래 대각선
for(int i=0; i<n; i++){
r++;
temp[r][c] = num;
num++;
}
n--;
if(n==0)
break;
//오른쪽
for(int i=0; i<n; i++){
c++;
temp[r][c] = num;
num++;
}
n--;
if(n==0)
break;
//위로 대각선
for(int i=0; i<n; i++){
r--;
c--;
temp[r][c] = num;
num++;
}
n--;
if(n==0)
break;
}
//temp값을 answer에 옮기기
int idx = 0;
for(int i=0; i<size; i++) {
for(int j=0; j<size; j++) {
if(temp[i][j] == 0) {
break;
}
answer[idx] = temp[i][j];
idx ++;
}
}
return answer;
}
}
728x90
반응형
'알고리즘 > PS - 프로그래머스' 카테고리의 다른 글
[프로그래머스 - Java] 가장 큰 정사각형 찾기 (0) | 2021.09.02 |
---|---|
[프로그래머스 - Java] 베스트앨범 (0) | 2021.09.01 |
[프로그래머스 - Java] 이중우선순위큐 (0) | 2021.08.31 |
[프로그래머스 - Java] N으로 표현 (0) | 2021.08.30 |
[프로그래머스 - Java] 입국심사 (0) | 2021.08.30 |