[프로그래머스, level2] 삼각 달팽이

문제

programmers.co.kr/learn/courses/30/lessons/68645

코딩테스트 연습 - 삼각 달팽이

 

풀이

 순서대로 map 에다가 숫자를 채워넣으면 "방향이 바뀌면서 숫자가 채워진다"라는 규칙을 발견할 수 있다. 이때 방향은 좌하향 → 오른쪽 → 좌상향 순서대로 변한다. 이때 '언제 방향이 변하나'를 보면 좌하향에서 오른쪽으로 변할 때는 이동하려는 row가 범위를 벗어날때 이다. 오른쪽에서 좌상향으로 방향이 변할 때는 이동하려는 column의 인덱스가 row보다 클때, 즉 column의 범위를 벗어날때이다. 그리고 좌상향에서 좌하향으로 방향이 바뀔 때는 이미 방문한 적있는 칸을 방문하려할 때이다. 

 

 

코드

class Solution {
    public int[] solution(int n) {
        int[][] map = new int[n][n];
        int[] answer = {};
        boolean[][] visited = new boolean[n][n];
        int endNum = n*(n+1)/2;
        answer = new int[endNum];
        int[] dx = {1, 0, -1};
        int[] dy = {0, 1, -1};

        int currentR = 0;
        int currentC = 0;
        int direction =0;

        for(int num = 1; num<=endNum; num++){
            //현재위치에 숫자 적기
            map[currentR][currentC] = num;
            visited[currentR][currentC] = true;

            //다음위치 구하기
            int nextR = currentR + dx[direction];
            int nextC = currentC + dy[direction];

            //다음위치가 범위를 벗어났거나 방문했던 곳인경우
            if(nextR>=n || nextC>nextR || visited[nextR][nextC]){
                direction = (direction+1)%3;
                nextR = currentR + dx[direction];
                nextC = currentC + dy[direction];
            }

            //위치 업데이트
            currentR = nextR;
            currentC = nextC;
        }
        
        int count = 0;
        for(int r = 0; r<n; r++){
            for(int c=0; c<n; c++){
                if(c<=r){
                    answer[count] = map[r][c];
                    ++count;
                }
            }
        }
        
        return answer;
    }
}