[프로그래머스] 삼각 달팽이 (팩토리얼, 메모이제이션)

문제 설명

정수 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]

 

문제 해설

제가 짠 알고리즘은 n을 5로 입력받았다고 가정했을때 아래와 같은 순서로 진행됩니다.

1. arr[factorial(5)] {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; 생성
2. 우측 순회 입력
    arr[15] {1,2,0,3,0,0,4,0,0,0,5,6,7,8,9}
3. 좌측 순회 입력
    arr[15] {1,2,12,3,0,11,4,0,0,10,5,6,7,8,9}
4. 우측 순회 입력
    arr[15] {1,2,12,3,13,11,4,14,15,10,5,6,7,8,9}

 

여기서 중요한 점은 우측 순회 입력 시

좌측 순회시는 

이 문제를 풀때는 factorial을 메모이제이션 하는것이 시간 복잡도가 낮습니다.

Factorial Memoization 전
* 테스트 1 〉 통과 (0.03ms, 52.6MB)
* 테스트 2 〉 통과 (0.02ms, 52.4MB)
* 테스트 3 〉 통과 (0.01ms, 52.6MB)
* 테스트 4 〉 통과 (2.61ms, 53.9MB)
* 테스트 5 〉 통과 (2.24ms, 53.9MB)
* 테스트 6 〉 통과 (3.16ms, 53.3MB)
* 테스트 7 〉 통과 (866.08ms, 114MB)
* 테스트 8 〉 통과 (380.19ms, 112MB)
* 테스트 9 〉 통과 (378.18ms, 110MB)

Factorial Memoization 후
* 테스트 1 〉 통과 (0.02ms, 52.9MB)
* 테스트 2 〉 통과 (0.02ms, 53.6MB)
* 테스트 3 〉 통과 (0.02ms, 52.4MB)
* 테스트 4 〉 통과 (0.81ms, 53.7MB)
* 테스트 5 〉 통과 (0.79ms, 53.8MB)
* 테스트 6 〉 통과 (0.86ms, 53.1MB)
* 테스트 7 〉 통과 (15.01ms, 110MB)
* 테스트 8 〉 통과 (16.80ms, 112MB)
* 테스트 9 〉 통과 (16.30ms, 111MB)

 

문제 풀이 코드

public class TriangularSnail {
    public static void main(String[] args) {
        int[] result = solution(6);

        for (int value : result) {
            System.out.print(value + " ");
        }
    }


    static int[] solution(int n) {
        int lastHead = n;    //오른쪽 순회 시 마지막으로 들러야하는 행
        int[] factorial = createFactorial(n);
        int[] answer = new int[factorial[n]];

        int rightCount = 0;   //배열을 오른쪽으로 순회한 횟수
        int leftCount = 1;    //배열을 좌측으로 순회한 횟수
        int count = 1;        //answer 배열에 순서대로 입력될 숫자
        int initCount = 0;

        while (count <= factorial[n]) {

            while (count <= factorial[n]) {      //down Input
                int i = factorial[initCount] + rightCount;
                answer[i] = count++;

                if (lastHead == answer[i - rightCount]) {
                    for (int j = i; j < i + answer[i - rightCount]; j++) {
                        if (count > factorial[n]) {
                            break;
                        } else if (answer[j] == 0) {
                            answer[j] = count++;
                        }
                    }
                    lastHead--;
                    break;
                }

                ++initCount;
            }

            ++rightCount;
            while (count <= factorial[n]) {    //up Input
                int i = factorial[initCount] - leftCount;
                answer[i] = count++;

                int nextI = factorial[--initCount] - leftCount;
                if (nextI < 0 || answer[nextI] > 0) {
                    leftCount++;
                    break;
                }
            }

            ++initCount;
        }

        return answer;
    }

    /**
     * 계속 순회 해도 되는지 판단합니다.
     */
    public static boolean isRun(int count, int maxNum) {
        return ;
    }

    /**
     * 팩토리얼 배열 생성
     * 팩토리얼 식 : i * (i+1) /2;
     * 예제 1)      5 * (5+1) /2;
     * = 15
     */
    static int[] createFactorial(int n) {
        int[] factorial = new int[n + 1];

        factorial[0] = 0;
        for (int i = 1; i <= n; i++) {
            factorial[i] = i * (i + 1) / 2;
        }

        return factorial;
    }
}