(프로그래머스) 삼각 달팽이

문제

https://programmers.co.kr/learn/courses/30/lessons/68645?language=java

접근

규칙이 있을 것이라고 생각하고 문제를 접근하게 되었다. 약간 큰 정삼각형을 그렸을 때 그 규칙을 찾아낼 수 있었다.

ex) n = 8 (숫자)

ex) n = 8 (인덱스)

패턴 확인

1) 삼각형 안의 삼각형

다음과 같이 삼각형 안에 삼각형... 의 연속임을 확인할 수 있었다.

2) 각 삼각형의 꼭대기 인덱스

인덱스 기준 0, 4, 12 ... 이렇게 증가한다. (맨 위에서부터 두 칸씩 떨어지며 +4, +8, +12, +16... 꼴로 나타난다.)

3) 각 삼각형의 변

삼각형1
좌측 : +1, +2, +3, +4, ...
아래 : +1, +1, +1, +1, ...
우측 : +2, +3, +4, +5, ...


삼각형2
좌측 : +3, +4, +5, +6, ...
아래 : +1, +1, +1, +1, ...
우측 : +4, +5, +6, +7, ...


삼각형3
좌측 : +5, +6, +7, ...
아래 : +1, +1, +1, ...
우측 : +6, +7, +8, ...


아래는 무조건 +1씩 증가하고 좌측 및 우측은 +1만큼 증가한 숫자만큼 증가한다.
(단, 첫 번째 원소와 두 번째 원소 간의 차가 안쪽 삼각형으로 들어갈수록 1씩 커진다.)

코드

class Solution {
    public int[] solution(int n) {
        int size = (n * (n + 1)) / 2; // 숫자 개수
        int[] answer = new int[size];
        int turn = 1; // 삼각형 차례
        int length = n; // 변 길이
        int num = 1; // 원소 번호
        int idx = 0; // 현재 인덱스
        
        while (num <= size) {      
            int start = 2 * turn - 1;
            
            if (length == 1) {
                answer[idx] = num;
                break;
            }
            
            // 왼쪽 변 채우기
            for (int i = start; i < start + length - 1; i++) {
                answer[idx] = num++;
                idx += i;
            }
            
            // 아래 변 채우기
            for (int i = 1; i < length; i++) {
                answer[idx++] = num++;
            }
            
            // 오른쪽 변 채우기
            for (int i = start + length - 1; i > start; i--) {
                answer[idx] = num++;
                idx -= i;
            }

            idx += 4 * turn++;
            length -= 3;
        }
        
        return answer;
    }
}

구현 자체는 어렵지 않지만 규칙을 찾아내고 인덱스를 적절히 적용할 줄 아는 능력이 필요한 문제였던 것 같다.