[프로젝트 오일러] 백만 이하로 시작하는 우박수 중 가장 긴 과정을 거치는 것은?

14번 문제같은 경우는 문제를 보자마자 설계가 바로 나왔기 때문에 분석 - 설계 - 의사코드 작성 - 코딩의 순서로 넘어갔고, 무난하게 풀 수 있었다.

느낀점중 하나는 TDD를 항상 할 필요는 없다는 것이다. 이미 설계가 있는 상황에서 굳이 TDD를 하는 것은 시간비용의 소모가 크기 때문에 비효율적이라는 생각을 했다.

다만 정상적인 동작을 보장하는 테스트 코드는 필요했기에 중간중간 테스트 코드를 작성하긴 했다.

time complexity는 O(n)이다. 

/**
 * 설계
 *
 * 입력값이 크므로 (100만) 시간 복잡도를 고려해야한다.
 *
 * 1. 객체가 필요하다.
 * 객체는 두가지 속성을 가진다.
 *      - 값 (1~100만)
 *      - 1이 될 때까지 걸린 과정의 횟수
 *
 * 2. 1~100만의 우박수에 대하여 각각 걸리는 과정을 계산한다.
 *
 * 3. 계산 후, 우박수 리스트에 넣는데 조건이 있다.
 *      - 현재 우박수 리스트에서 최고 과정 값보다 클 경우만 넣는다.
 *          - 최고 값만 뽑는 것이므로, 최고 값보다 작은 값이 들어가는건 의미가 없다.
 *
 * 알고리즘 도출
 *
 * 1. 루프 시작
 * 2. 각 인덱스 값에 대하여 과정 계산.
 * 3. 조건 비교후 우박수 리스트에 집어넣음
 *      - 최고값 가져오는 함수 필요
 * 4. 루프 종료 후 우박수 리스트에서 과정 수가 제일 큰 값 반환
 * 5. 해당 우박수 객체에서 number값을 꺼냄.
 *
 */

처음 설계를 할 때, 시간 복잡도에 대한 부분을 해결하는 데에 초점을 맞췄다.

단순하게 풀 수도 있었지만, 입력값이 100만이기 때문에 중복되는 계산이 발생하면 계산 비용이 상당히 많이 들어갈 것으로 예상되었다. 그래서 우박수 리스트에 우박수를 집어넣을 때, 우박수 리스트가 가지고 값들 중 최대값보다 큰 경우만 push하도록 하였다. 

(우박수 리스트는 배열이기 때문에 배열 요소에 바로 접근할 수 있어, 시간 복잡도가 O(1)이기 때문에 자주 호출해도 부담이 없다.)

만약 자바로 작성하였다면, Map이나 Dictionary 등 중복을 제거할 수 있는 방법을 찾았을 것이다.

테스트 케이스

<script>
    var longestCollatz = new LongestCollatz();

    QUnit.test( "결과값", function( assert ) {
            assert.equal(longestCollatz.getLargestNum(1000000), 837799);
        }
    );

    QUnit.test("13에 대한 우박수 테스트", function (assert) {
                assert.equal(longestCollatz.createHailstone(13)["processCnt"], 10);
            }
    );

    QUnit.test( "가장 큰 값 가져오는 테스트", function( assert ) {
                assert.equal(longestCollatz.getLargestProcessCnt(longestCollatz.createHailStones(13)), 20);
            }
    );

</script>

로직

function LongestCollatz(){
    /**
     * main method
     * @param inputSize
     * @returns {*}
     */
    function getLargestNum(inputSize){
        var hailstones = createHailStones(inputSize); //우박수 리스트 반환
        return getLargestNumber(hailstones); //우박수 리스트들 진행 과정이 제일 긴 우박수의 number를 반환
    }

    /**
     * 진행과정이 제일 긴 우박수의 number을 반환
     * @param hailstones
     * @returns {*}
     */
    function getLargestNumber(hailstones) {
        return hailstones[hailstones.length - 1]["number"];
    }

    /**
     * 진행과정이 제일 긴 우박수의 진행과정 수를 반환
     * @param hailstones
     * @returns {*}
     */
    function getLargestProcessCnt(hailstones) {
        if(hailstones.length === 0){
            return 0;
        }
        var largestHailstone = hailstones[(hailstones.length - 1)];
        return largestHailstone["processCnt"];
    }

    /**
     * 우박수 리스트를 생성
     * @param inputSize
     * @returns {Array}
     */
    function createHailStones(inputSize) {
        var hailstones = [];
        var hailstone = {};
        for (var index = 1; index <= inputSize; index++) {
            //우박수를 구하는 과정
            hailstone = createHailstone(index);
            //우박수를 리스트에 넣을지 여부 결정
            if (hailstone["processCnt"] > getLargestProcessCnt(hailstones)) {
                hailstones.push(hailstone);
            }
        }

        return hailstones;
    }

    /**
     * 진행과정 수에 대한 속성을 가진 우박수 객체를 생성
     * @param number
     * @returns {{number: *}}
     */
    function createHailstone(number) {
        var result = {
            number : number
        };
        var processCnt = 1;

        while(true){
            if(isEven(number)){
                number = number / 2;
            }else {
                number = 3 * number + 1;
            }
            processCnt++;
            if(number === 1){
                break;
            }
        }
        result["processCnt"] = processCnt;
        return result;
    }

    /**
     * 입력 값이 짝수인지 판별
     * @param number
     * @returns {boolean}
     */
    function isEven(number) {
        return number % 2 === 0;
    }

    return {
        createHailstone : createHailstone,
        getLargestNum : getLargestNum,
        createHailStones : createHailStones,
        getLargestProcessCnt : getLargestProcessCnt
    };
};