Home P68645. 삼각 달팽이
Post
Cancel

P68645. 삼각 달팽이

문제

image


제출 코드

  • 사용 알고리즘 : 구현


배열돌리기 삼각형 버전이다. 어떻게 해야하나 고민했는데, 삼각형의 각 변 위에서 다음칸으로 움직일 때 변화하는 i, j의 변화량을 di와 dj 배열에 저장하고 사용하는 방식으로 했다.

같은 방향으로 지속해서 넘어가다가 방향이 변하는 지점이 오면, 이전에 잘못 변화했던 값을 돌려놓고 제대로 된 변화량을 더해줘야 하는데 그 부분을 깜빡해서 틀렸다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.*;

class Solution {
    public int[] solution(int n) {
        int[] di = {1, 0, -1};
        int[] dj = {0, 1, -1};

        int[][] tri = new int[n][n];
        int max = ((1+n)*n)/2;
        int d=0, ni=-1, nj=0;
        for(int i=1; i<=max; i++){
            ni += di[d];
            nj += dj[d];
            if(ni<0 || ni>=n || nj<0 || nj>=n || tri[ni][nj]!=0){
                ni -= di[d];
                nj -= dj[d];
                d = (d+1) % 3;
                ni += di[d];
                nj += dj[d];
            }
            tri[ni][nj] = i;
        }

        int[] answer = new int[max];
        int idx = 0;

        for(int i=0; i<n; i++){
            for(int j=0; j<=i; j++) answer[idx++] = tri[i][j];
        }

        return answer;
    }
}
This post is licensed under CC BY 4.0 by the author.