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

문제내용

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

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

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

---

제한사항

• n은 1 이상 1,000 이하입니다.

---

문제풀이

문제를 풀어놓고 다른 사람들 풀이를 봤는데, 다른분들은 for문을 이용해 푸신들이 많았다. 효율적인 측면에선 for문으로 푼 방법이 더 좋다고 생각했지만 그래도 좀 복잡할지라도 bfs로 푼 방법도 있다는걸 말하려고한다.

 

먼저 반시계방향으로 숫자를 채워간다는 말은 2차원 배열로 봤을때

아래 -> 오른쪽 -> 대각선 방향으로 숫자가 다 채워질때까지 반복한다는 말이다.

그리고 모든 숫자가 채워졌을때 마지막 숫자가 어떤 숫자가 될지 알수 있다면, 언제 끝내야하는지도 알수 있다.

 

마지막 숫자를 찾기 위해 규칙을 찾아보면

n=1,  f(n)=1

n=2,  f(n)= f(n-1)+n = 1+2 = 3

n=3,  f(n)= f(n-1)+n = 3+3 = 6

n=4,  f(n)= f(n-1)+n = 6+4 = 10

n=5,  f(n)= f(n-1)+n = 10+5 = 15

n=6,  f(n)= f(n-1)+n = 15+6 = 21

이라는걸 알수 있고, 점화식이라고 생각해도된다.

따라서 bfs로 아래 -> 오른쪽 -> 대각선 -> 아래 -> 오른쪽 -> 대각선 ..... 을 순회하면서 마지막 숫자가 나왔을때 반복문을 멈추면된다.

 

참고로 나는 dp를 이용해 마지막 숫자를 저장했는데, 이거 등차수열이라고 한다.

등차수열의 합: (n*(n+1))/2

---

코드

import java.util.*;

public class Solution {
	static private int[] dx = {1,0,-1};//아래, 대각선
	static private int[] dy = {0,1,-1};//오른쪽, 대각선
	static private class Node{
		int x;
		int y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
    public static int[] solution(int n) {
    	if(n==1) {//1일땐 걍 바로 반환
    		int[] answer = {1};
    		return answer;
    	}
    	
    	int[] dp = new int[n];//마지막 숫자를 저장해놓을 배열
        int[][] arr = new int[n][n];//1씩 카운트를 할 배열
        boolean[][] check = new boolean[n][n];//방문 배열
        
        dp[0] = 1;
        for(int i=1; i<n; i++)
        	dp[i] = dp[i-1]+(i+1);
        
        
        //초기값 추가
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0,0));
        check[0][0] = true;
        arr[0][0] = 1;
        int dir = 0; //방향
        
        //bfs 시작
        while(!q.isEmpty()) {
        	Node cur = q.poll();
        	
        	int nx = cur.x + dx[dir];
        	int ny = cur.y + dy[dir];
        	
        	//배열범위 밖으로 넘어가면 방향 재정의
        	if(nx<0 || ny<0 || nx>=n || ny>=n) {
        		if(dir==0) dir = 1;
        		else if(dir==1) dir = 2;
        		q.add(cur);
        		continue;
        	}
        	
        	//이미 방문한 위치면 방향 재정의
        	if(check[nx][ny]) {
        		if(dir==2) dir = 0;
        		else if(dir==0) dir = 1;
        		else if(dir==1) dir = 2;
        		q.add(cur);
        		continue;
        	}
        	
        	check[nx][ny] = true;//방문
        	arr[nx][ny] = arr[cur.x][cur.y]+1;//카운트 증가
        	if(arr[nx][ny]==dp[dp.length-1]) break;//마지막 숫자가 됐을때 종료.
        	q.add(new Node(nx,ny));
        }
        
        //이 아래로는 그냥 배열에 숫자를 차례대로 채우는 과정
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<n; i++) {
        	int[] temp = arr[i];
        	for(int j=0; j<temp.length; j++) {
        		if(temp[j]==0) break;
        		list.add(temp[j]);
        	}
        }
        
        int[] answer = new int[list.size()];
        for(int i=0; i<list.size(); i++) {
        	answer[i] = list.get(i);
        	System.out.print(answer[i]+" ");
        }
        
        return answer;
    }
}

---

마치며

이번 풀이에선 bfs로 풀긴했지만 for문으로 한번 풀어보는 것도 좋을거라고 생각한다.