프로그래머스 : 삼각 달팽이 (Java, Lv.2, 배열)

 

 

 

잘못된 풀이 

class Solution {
    public int[] solution(int n) {
        int maxValue = n*(n+1)/2; // 최대숫자값
        int[] answer = new int[maxValue];
        int[][] arr = new int[n][n];
        int num = 1;
        for (int k = 0; k < n ; k++) {
            int i = k, j = k; // i: 행, j: 열
            boolean yn = true;
            while (yn || num <= maxValue) {
                if (i == k+1 && j == k+1) {
                    yn = false;
                } else if (j == k && i < n-1-k) {
                    i++;
                } else if (i == n-1-k && j < n-1-k) {
                    j++;
                } else {
                    i--;
                    j--;
                }
                arr[i][j] = num;
                num++;
            }
        }
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j= 0; j <= i; j++) {
                answer[index] = arr[i][j];
                index++;
            }
        }
        return answer;
    }
}

 

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 5
	at Solution.solution(Unknown Source)
	at SolutionTest.lambda$main$0(Unknown Source)
	at SolutionTest$SolutionRunner.run(Unknown Source)
	at SolutionTest.main(Unknown Source)
테스트 결과 (~˘▾˘)~
3개 중 0개 성공

 

정답

아이디어1(비효율적)

class Solution {
    public int[] solution(int n) {
        int[][] triangle = new int[n][n];
        int v = 1; // 채워갈 숫자
        int x = 0;
        int y = 0;
        
        while (true) {
            // 아래로 이동
            while (true) {
                triangle[y][x] = v++;
                if (y+1 == n || triangle[y+1][x] != 0) break;
                y+=1;
            }
            // 오른쪽으로 더 갈 수 있는지 확인
            if(x+1 == n || triangle[y][x+1] != 0) break;
            x+=1;
            
            // 오른쪽으로 이동
            while (true) {
                triangle[y][x] = v++;
                if (x+1 == n || triangle[y][x+1] != 0) break;
                x+=1;
            }
            // 왼쪽 대각선 방향으로 갈 수 있는지 확인
            if (triangle[y-1][x-1] != 0) break;
            x-=1;
            y-=1;
            
            // 왼쪽 대각선으로 이동
            while (true) {
                triangle[y][x] = v++;
                if (x-1 == 0 || y-1 == 0 || triangle[y-1][x-1] != 0) break;
                x-=1;
                y-=1;
            }
            if (y+1 == n || triangle[y+1][x] != 0) break;
            y+=1;
        }
        int[] answer = new int[v-1];
        int index = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                answer[index++] = triangle[i][j];
            }
        }
        return answer;
    }
}

 

 

아이디어2 (효율적)

class Solution {
    private static final int[] dx = {0, 1, -1};
    private static final int[] dy = {1, 0, -1};
    public int[] solution(int n) {
        
        int[][] triangle = new int[n][n];
        int v = 1; // 채워갈 숫자
        int x = 0;
        int y = 0;
        int d = 0;
        
        while (true) {
            
            triangle[y][x] = v++;
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx == n || ny == n || nx == -1 || ny == -1 || triangle[ny][nx] != 0) {
                // 방향 전환
                d = (d+1) % 3;
                nx = x + dx[d];
                ny = y + dy[d];
                if (nx == n || ny == n || nx == -1 || ny == -1 || triangle[ny][nx] != 0) break;
            }
            x = nx;
            y = ny;
        }
        int[] answer = new int[v-1];
        int index = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                answer[index++] = triangle[i][j];
            }
        }
        return answer;
    }
}