[알고리즘] 프로그래머스 삼각 달팽이 (레벨 2) / 자바 java 풀이

 

분명 이런 삼각 달팽이, 별 만들기, 별 찍기, 달팽이 뭐시기... 이런 거만 코딩 처음 배울 때 내내 푼 기억이 있는데도 왜 풀 때 마다 고민하고 풀 때 마다 어려운지 모르겠다ㅠㅠㅋㅋㅋ

 

📑 삼각 달팽이

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

문제 설명

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

---

제한 사항

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

---

입출력 예

n	result
4	[1,2,9,3,10,8,4,5,6,7]
5	[1,2,12,3,13,11,4,14,15,10,5,6,7,8,9]
6	[1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11]

 

✏️ 문제 해결 방법

1. 좌표 이동하며 값 채워주기

좌표 이동문제로 생각하고 그렇게 접근하고자 하였다. 우선 2차원 배열을 생각하였고 2차원 배열 내에서 이동하며 값이 채워져 있거나 배열을 넘어서면 (인덱스가 0 보다 작거나 n 이상이면) 방향을 바꿔 계속해서 값을 채워나가고자 하였다.

삼각달팽이에서는 1 부터 n * (n + 1) / 2 만큼의 수까지 증가시켜 채워주면 되기 때문에 마지막 값이 항상 정해져 있기 때문이다.

int[][] triangle = new int[n][n];
        
int value = 1;
int x = 0;
int y = 0;
        
// 아래, 오른쪽, 대각선
int dx = {1, 0, -1};
int dy = {0, 1, -1};
        
int idx = 0;
        
while(value <= n * (n+1) / 2) {
	triangle[x][y] = value++;
            
	int nx = x + dx[idx];
	int ny = y + dy[idx];
            
	if(nx >= n || nx < 0 || ny >= n || ny < 0 || triangle[nx][ny] != 0) {
		idx = (idx + 1) % 3;
		nx = x + dx[idx];
		ny = y + dy[idx];
	}
	x = nx;
	y = ny;
}

 

2. 리스트에 넣어 배열로 변환하기

그리고 이 결과를 리스트에 넣어 리스트를 배열로 변환하여 return 하였다.

 

 

전체 코드

class Solution {
    public int[] solution(int n) {
        
        int[][] triangle = new int[n][n];
        
        int value = 1;
        int x = 0;
        int y = 0;
        
        // 아래, 오른쪽, 대각선
        int dx = {1, 0, -1};
        int dy = {0, 1, -1};
        
        int idx = 0;
        
        while(value <= n * (n+1) / 2) {
            triangle[x][y] = value++;
            
            int nx = x + dx[idx];
            int ny = y + dy[idx];
            
            if(nx >= n || nx < 0 || ny >= n || ny < 0 || triangle[nx][ny] != 0) {
                idx = (idx + 1) % 3;
                nx = x + dx[idx];
                ny = y + dy[idx];
            }
            x = nx;
            y = ny;
        }
        
        List<Integer> answer = new ArrayList<>();
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j <= i ; j++) {
                answer.add(triangle[i][j]);
            }
        }

        return answer.stream().mapToInt(i -> i).toArray();
    }
}

 

 

🕸️ 문제 풀이 소감

이번에 다시 풀면서는 좌표 이동문제로 생각하면서 풀었는데 이전에 풀었던 풀이법을 다시 살펴 보았다. 이전에 풀었던 풀이법은 오히려 이해가 잘 안됐었는데 구글링해서 나오는 대부분의 답들과 비슷했다. 아마... 보고 푼건가?ㅋㅋㅋㅋ 

 

접근 자체는 비슷한데 코드 자체가 쉽게 와닿지 않았다.. 아마 좌표 이동 문제가 이제는 꽤나 익숙해져서 그런 듯 하다. 처음 좌표 이동 문제들을 접했을 때는 나랑 절대 절대 절~~대 익숙해 지지 않을 것 같았고 -1, 1, 0, 0  이게 뭘 의미하는지도 몰랐는데 이제는 이걸 이해하고 어떻게 이동할지도 생각하는 게 너무 신기하기도 하다. 

 

오히려 재미있는 (?) 듯 하다. 스트림은 기억을 잘 못 할 것 같아 되도록이면 잘 안 쓰려고 하는데 좌표가 익숙해 진 것을 보며 이제 스트림과도 익숙해지려고 한다! ㅎㅎ

 

---

 

잘못된 부분이 있거나, 궁금한 부분이 있다면 댓글 부탁드립니다 🤗 

감사합니다 !