프로그래머스 - 삼각 달팽이

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

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

 

 

 

 

 

 

풀이를 어떻게 해야할지 도저히 감이 안잡혀서 빠르게 구글링을 했다. 구글링을 해보니 좌표들을 나열해 규칙성을 찾아 푼 풀이를 봤다. 그냥 풀이를 읽었을 때는 이해가 되지 않았지만, 직접 따라쳐보면서 나도 종이에 좌표를 그려가면서 하니 이해가 되기 시작했다.

 

 

 

 

 

1. 3가지 패턴이 반복 :  아래, 오른쪽, 위대각선 -> 나머지 연산을 이용해, 각각 0인 경우, 1인 경우, 2인 경우로 나눠 반복하게 한다. 

 

2. 각각의 패턴에 맞는 좌표의 규칙성을 찾는다.

 

좌표가 (x, y)라면,

아래 : x가 증가된다.

오른쪽 : y가 증가된다.

위대각선 : x가 감소하고, y도 감소한다.

 

3. count를 세며 배열에 값을 넣는다.

 

 

 

 

 

코드

class Solution {
    public int[] solution(int n) {
        int[] answer = new int[n * (n + 1) / 2];
        int[][] arr = new int[n][n];
        
        int count = 1;
        int x = -1;
        int y = 0;
        
        //아래, 오른쪽, 위로 대각선이 반복된다
        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 { //위로 대각선
                    x--;
                    y--;
                }
                
                arr[x][y] = count++;
            }
        }
        
        //정답 도출
        int k = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(arr[i][j] != 0) {
                    answer[k++] = arr[i][j];
                }
            }
        }
        
        return answer;
    }
}

 

 

 

 

 

참고

https://minhamina.tistory.com/58

[프로그래머스 - Java] 삼각 달팽이(월간 코드 챌린지 시즌1)

 

 

 

 

 

 

 

번외 - 사각형

응용해서 사각형으로 풀어봤다. 사각형이 더 어렵다.

 

public static int[][] solution(int n) {
	int[][] answer = new int[n][n];
		
	int count = 1;
	int x = 0;
	int y = -1;
		
	int k = n;
	for(int i = 0; i < n * 2 - 1; i++) {
		if(i % 2 == 1) {
			k--;
		}
			
		for(int j = 0; j < k; j++) {
			if(i % 4 == 0) { //오른쪽
				y++;
			} else if(i % 4 == 1) { //아래로
				x++;
			} else if(i % 4 == 2) { //왼쪽
				y--;
			} else { //위로
				x--;
			}
				
			answer[x][y] = count++;
		}
			
	}
		
	return answer;
}