프로그래머스 - 삼각 달팽이(Java, LV2)

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

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

풀이

쉬운 문제처럼 보였으나 규칙성을 찾는데 생각보다 오래걸렸다...

수학 규칙을 추론하고 검증하는데 조금 무뎌진거 같은 느낌이었다.

 

기본적으로 전체 큰 삼각형의 특성을 살펴보면 된다.

왼쪽아래 대각선으로 내려오거나(Down) 

오른쪽으로 지나가거나(Side)

왼쪽위 대각선으로 올라가거나(Up)

세 가지 중 하나이다.

그리고 각 방향의 길이는 n, n-1, n-2, ... ,1 까지 반복된다.

 

즉, 그림으로 표현하면 다음과 같다.

정리하면 로직은 다음과 같다.

• 각 단계(stg)는 Down(0) - Side(1) - Up(2) 순으로 반복된다
• 단계의 길이는 n에서부터 1까지 작아진다.
• 각 단계별로 값(val)은 1씩 증가
• 값을 입력할 위치(idx)는 방향에 따라 달라짐(Down-> 특정값(cnt)더하기 / Side -> 1 더하기 / Up -> 특정값(cnt) 빼기) 

class Solution {
    public int[] solution(int n) {
        int[] answer = new int[(n* (n+1))/2];
        // n번   내려가기 / n-1번 옆으로가기 / n-2번 올라가기
        // n-3번 내려가기 / n-4번 옆으로가기 / n-5번 올라가기...
        // n-n번이 될때까지
        int val = 1; int idx = 0; int cnt = 0;
        int stg = 0; // 0 Down 1 Side 2 Up
        int stg_n = n;
        
        while(n>0){
            // Down
            if(stg == 0){
                idx = idx + cnt;
                answer[idx] = val++;
                cnt++;
                stg_n--;
                // Down -> Side
                if(stg_n == 0){
                    stg = 1; // Side
                    stg_n = --n;
                }
            }
            // Side
            else if(stg == 1){
                answer[++idx] = val++;
                stg_n--;
                // Side -> Up
                if(stg_n == 0){
                    stg = 2; // Up
                    stg_n = --n;
                }
            }
            // Up
            else{
                idx = idx - cnt;
                answer[idx] = val++;
                cnt--;
                stg_n--;
                // Up -> Down
                if(stg_n == 0){
                    stg = 0; // Down
                    stg_n = --n;
                }
            }
        }
        return answer;
    }
}