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

문제 생략

풀이

class Solution {
    public int[] solution(int n) {
        int len = n*(n+1)/2;
        int[] ans = new int[len]; // 정답에 쓰일 배열
        
        int num = 1; //현재 숫자
        int i = 0; // 현재 숫자가 들어갈 인덱스
        int r = 1; // 현재 행의 길이
        
        int moveOfIndex[] = {1, 1, -1}; // 숫자가 들어갈 부분(즉, 인덱스)의 이동 필터
        int d = 0; // 어떤 이동필터를 쓰고있는지 나타냄 (0, 1, 2) 인덱스 내에서만 이동
        
        int cnt = 1; // 숫자가 들어간 횟수. len보다 클 시 달팽이 채우기 중단
        
        while(cnt++ <= len){
            // 1. 현재 위치숫자 넣기
            ans[i] = num++; 
            
            // 2. 다음 이동 고려
            if(i + moveOfIndex[d]>=len || 
               ans[i + moveOfIndex[d]] != 0) 
                d = (d+1)%3; 

            // 3. 다음 이동
            i += moveOfIndex[d];
            
            // 이동필터에 따라 다음 위치 계산에 쓰일 행의 길이가 달라짐
            if(d == 0) r++; 
            else if(d == 2) r--;
            moveOfIndex[0] = r; moveOfIndex[2] = -r; // r 값 갱신
        }
        return ans;
    }
}

• 배열의 길이는 n(n+1)/2
• num이 숫자, r이 행의 번호이자 행의 길이, i가 인덱스이다.
• arr[i] = num++ <- 기본적으로 이렇게 배열에 숫자가 들어갈것
• 그러나 i의 위치는 가변적인데, 아래 이동 필터와 같은 규칙으로 바뀜을 확인할 수 있음
• d = {i+r, i+1, i-r} / 왼쪽 아래로 내려갈때, 오른쪽으로 갈 때, 왼쪽 위로 올라갈 때
• 이동 필터 선택 조건은 다음 이동 시 배열에 숫자가 있을 때 또는 배열을 벗어났을 때.

결과

후기

인덱스의 다음 위치를 알아내는 데는 시간을 크게 쓰지 않았지만 구현이 생각보다 어려웠음. 특히 moveOfIndex에 들어가는 r값을 바꿔줘야 할 때 어떻게 해야 가독성도 좋고 효율적으로 바꿀 수 있을 지 고민했다. (결국 그냥 넣긴 했지만)