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

# 문제

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

프로그래머스

정수 n이 매개변수로 주어집니다.

다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

 

# 풀이 (자바) 

import java.util.Arrays;
class Solution {
    public int[] solution(int n) {
          int[][] triangle = new int[n][n];
	        
	        int x = 0; // x 좌표
	        int y = 0; // y 좌표 
	        int num = 1; // 셀 안에 들어갈 수 
            
            int k = 0; // answer 의 인덱스를 저장할 수 
	        int count = n - 1; // 방향이 바뀔 때 마다 달팽이가 움직여야하는 칸 수 
	        int sellNum = 0; // 전체 셀의 개수
	        
            // 전체 셀의 개수 계산 
	        for (int i = 1; i < n + 1; i++) {sellNum += i;}
	        
	        int[] answer = new int[sellNum];
	        
	       while(true) {
	    	   if (count == 0) {count = 1;} // n = 4 의 10 처럼, count가 0이 되는 상황에도 한 번은 달팽이가 움직여야하기 때문에 1로 선언해준다. 
	    	   for (int i = 0; i < count; i++) {
	    		   if(sellNum == 0) { break; }
	    		   triangle[x][y] = num; 
	    		   x++;
	    		   num++;
	    		   sellNum--;
	    	   }
	    	   for (int i = 0; i < count; i++) {
	    		   if(sellNum == 0) { break; }
	    		   triangle[x][y] = num;
	    		   y++;
	    		   num++;
	    		   sellNum--;
	    	   }
	    	   for (int i = 0; i < count; i++) {
	    		   if(sellNum == 0) { break; }
	    		   triangle[x][y] = num;
	    		   x--;
	    		   y--;
	    		   num++;
	    		   sellNum--;
	    	   }
	    	  x = x + 2;
	    	  y = y + 1;

	    	  count -= 3; // 한 바퀴 돌 때 마다, 채우는 칸의 개수가 3개씩 줄음  

	       }

	       // triangle 2차원 배열을 1차원 배열인 answer 로 옮기기
	       while (k < answer.length) {
	    	   for (int i = 0; i < n; i++) {
	    		   for (int j = 0; j < i + 1; j++) {
	    			   answer[k] = triangle[i][j];
	    			   k++;
	    		   }
	    	   }
	       }
	       return answer;
    }
}

 

#느낀점

알고리즘 짜는 게 참 알듯말듯 했다. 내가 풀이한 방법은 

1. 전체 셀의 개수를 계산한 뒤, 

2. 각 방향마다 count 개수에 맞게 셀을 채우고

3. 한 바퀴를 돌아올 때 count 수를 조정해서 계속 채워나가는 방식으로 생각했다. 

 

n = 5 일 경우, 시작점인 [0][0]을 기준으로 count 의 수는 4이다.

↓
↓	↖
↓		↖
↓			↖
→	→	→	→	↖

먼저 첫번째 테두리는 이렇게 4칸씩 이동하게 된다. 

한 바퀴를 돌았으니 count - 3 을 통해 count 는 1이 되게 된다.

여기서 주의할 점은 보라색 방향이 4칸을 이동했을 때, for 문 안의 x--; y--;로 인해 최종 도착지는 [0][0] 이 된다. 

안쪽의 비어있는 셀을 채우기 위한 달팽이의 시작점은 [2][1]이 되어야 하기때문에 x 에는 +2 를, y에는 +1 을 해준다. 

이것은 달팽이 한 바퀴가 다 도는 모든 경우에 해당되므로 while 문이 끝나기 전 for 문 밖에서 입력해주었다. 

 

↓
↓	↖
↓	↓	↖
↓	→	↖	↖
→	→	→	→	↖

두번째 바퀴의 count 는 1이므로, 안쪽은 이렇게 1칸씩 채워진다. 

 

또 하나 생각해야 하는 점은, n = 4 의 경우와 같이 count 가 3일 경우 , 그 다음 count 0 이 되게 되는데, 

이렇게 되면 채우지 못한 한 개의 셀이 정 중앙에 남게된다 (아래 표 참고).

↓
↓	↖
↓	이곳!	↖
→	→	→	↖

따라서, count 가 0일 때, 1로 변경해주는 조건 : if (count == 0) {count = 1;} 을 추가해주었다. 

 

 

테스트를 통과하고 다른 사람들의 풀이를 보는데... 

		if (i % 3 == 0) {
                    ++x;
                } else if (i % 3 == 1) {
                    ++y;
                } else if (i % 3 == 2) {
                    --x;
                    --y;
                }
                matrix[x][y] = num++;

이렇게 3으로 나눠서 딱 나누어 떨어질 때, 나머지가 1일 때, 2일 때로 푼 사람이 있더라!!! 홀리몰리...

이 알고리즘이 나는 제일 깔끔한 것 같았다. 불필요한 포문과 반복들을 지워주는 게 정말 깔끔하더라. 

다음에는 이런 코드를 짤 수 있도록 더 생각하면 좋겠다!