CodeWars 아흔 여섯 번째 문제

Hamming Numbers

public static long hamming(int n) {

    List<Long> list = new ArrayList<Long>();

    for(int two = 0; Math.pow(2, two) < Long.MAX_VALUE; two++) {

        for(int three = 0; Math.pow(2, two) * Math.pow(3, three) < Long.MAX_VALUE; three++) {

            for(int five = 0; Math.pow(2, two) * Math.pow(3, three) * Math.pow(5, five) < Long.MAX_VALUE ; five++) {
                list.add((long) (Math.pow(2, two) * Math.pow(3, three) * Math.pow(5, five)));
            }
        }
    }

    Collections.sort(list);

    return list.get(n-1);
}

• 최근 4kyu 문제 3개를 풀었는데 2개를 풀지 못하고 하나는 포스팅 했고 하나는 포스팅 자체도 포기했다.
• 문제가 점점 어려워져서 그런가 보다. 조건들이 까다롭기도 하고 문제가 이해가 잘 되지 않았다.
• 100문제 (1000점을 채우고)를 채우고 프로그래머스로 넘어가려고 한다. 실제 기업들이 내는 문제이기 때문.
• 어쨌든, 이 문제의 경우 나는 삼 중 for으로 풀었다. 처음에는 timeout이 발생했다. 너무 많은 계산 때문이다. 그러나 두, 세 번째 for문에 계산 수를 확 줄여 줄 수 있게 조건을 더 넣었다. 그리고 마지막 list를 정렬하여 출력했다.
• 그러나 역시!! BEST 코드의 경우는 남달랐다.
• 맨 처음 3와 5를 비교한다. 3이 작으니까 다음 2랑 비교한다. 역시나 2가 작기 때문에 2를 배열 h의 두 번째 인덱스에 넣는다.
• 이때 h[1]은 2와 같기 때문에 2와 h[1]을 곱한다. 그럼 4, 3, 5가 된다. 이때 h[1]이 무엇이냐면 코드에서 h[++i]가 있는 부분인데 i, j, k는 각각 2,3,5의 제곱근을 얘기한다. 따라서 i를 1증가 시킨 h[1]은 2이므로 2와 2를 곱하여 4, 3, 5가 된다.
• 다시 돌아서 h[2]에 들어갈 숫자를 찾는다. 3과 5를 또 비교해서 3이 나온다. 이번에는 4와 3을 비교했는데 3이 작으므로 h[2]에 넣는다. h[2]는 3과 같기 때문에 h[1]을 곱해준다.여기서 h[1]은 h[++j]인데 j가 0이었으므로 1증가시켜서 h[1]이 된다. h[1]은 2이므로 2와 3을 곱하여 6이 된다. 그럼 최종 4,6,5가 된다.
• 이번에는 4,6,5중 4가 가장 작으므로 4를 h[3]에 넣고 h[++i]인 즉, h[2] (i가 1이었는데 1증가 했으므로) 3이기 때문에 2와 h[2] (즉, 3) 를 곱한 6이 된다.
• 이번에는 6, 6, 5인데 5가 가장 작으므로 h[4]에 5를 넣는다. h[4]는 5이므로 h[++k] (k는 0이므로 1증가)인 즉, h[1]과 5를 곱한다. 그러머녀 h[1]은 2이므로 5를 곱하여 10이 되고, 최종 6,6,10이 된다.
• 이번은 6,6,10을 비교하는데 6,6 이 같기 때문에 h[5]에 6을 넣고 h[5]가 6이므로 6(x2), 6(x3)과 같기 때문에 각각 h[++i] , h[++j]를 2와 3과 곱한다. 이때 h[++i]는 4이고 h[++j] 3이므로 각각 2와 3을 곱하면 8, 9가 된다. 그러면 최종 8, 9, 19이 된다.
• 이런 식으로 배열을 꽉 채워서 마지막 인덱스를 출력한다.
• 후… 코드를 해석하면서 정말 어렵다는 생각이 든다…ㅠㅠ

public static long hamming(int n) {
    long[] h = new long[n];
    h[0] = 1;
    long x2 = 2, x3 = 3, x5 = 5;
    int i = 0, j = 0, k = 0;

    for (int index = 1; index < n; index++) {
        h[index] = Math.min(x2, Math.min(x3, x5));
        
        /* 임의로 넣은 코드 
        System.out.println("전 위치: " + i + " " + j + " " + k);
        System.out.println("전 배수: " + x2 + " " + x3 + " " + x5);

        for(int x = 0; x < n ; x++) {
            System.out.print(h[x] + " ");
        }

        System.out.println();*/

        if (h[index] == x2) x2 = 2 * h[++i];
        if (h[index] == x3) x3 = 3 * h[++j];
        if (h[index] == x5) x5 = 5 * h[++k];

        /* 임의로 넣은 코드 
        System.out.println("후 위치: " + i + " " + j + " " + k);
        System.out.println("후 배수: " + x2 + " " + x3 + " " + x5);

        System.out.println(); */
    }

    return h[n - 1];
}
/ * -----------------------------------*/
전 위치: 0 0 0
전 배수: 2 3 5
1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
후 위치: 1 0 0
후 배수: 4 3 5

전 위치: 1 0 0
전 배수: 4 3 5
1 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
후 위치: 1 1 0
후 배수: 4 6 5

전 위치: 1 1 0
전 배수: 4 6 5
1 2 3 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
후 위치: 2 1 0
후 배수: 6 6 5

전 위치: 2 1 0
전 배수: 6 6 5
1 2 3 4 5 0 0 0 0 0 0 0 0 0 0 0 0 0 
후 위치: 2 1 1
후 배수: 6 6 10

전 위치: 2 1 1
전 배수: 6 6 10
1 2 3 4 5 6 0 0 0 0 0 0 0 0 0 0 0 0 
후 위치: 3 2 1
후 배수: 8 9 10

전 위치: 3 2 1
전 배수: 8 9 10
1 2 3 4 5 6 8 0 0 0 0 0 0 0 0 0 0 0 
후 위치: 4 2 1
후 배수: 10 9 10

전 위치: 4 2 1
전 배수: 10 9 10
1 2 3 4 5 6 8 9 0 0 0 0 0 0 0 0 0 0 
후 위치: 4 3 1
후 배수: 10 12 10

전 위치: 4 3 1
전 배수: 10 12 10
1 2 3 4 5 6 8 9 10 0 0 0 0 0 0 0 0 0 
후 위치: 5 3 2
후 배수: 12 12 15

전 위치: 5 3 2
전 배수: 12 12 15
1 2 3 4 5 6 8 9 10 12 0 0 0 0 0 0 0 0 
후 위치: 6 4 2
후 배수: 16 15 15

전 위치: 6 4 2
전 배수: 16 15 15
1 2 3 4 5 6 8 9 10 12 15 0 0 0 0 0 0 0 
후 위치: 6 5 3
후 배수: 16 18 20

전 위치: 6 5 3
전 배수: 16 18 20
1 2 3 4 5 6 8 9 10 12 15 16 0 0 0 0 0 0 
후 위치: 7 5 3
후 배수: 18 18 20

전 위치: 7 5 3
전 배수: 18 18 20
1 2 3 4 5 6 8 9 10 12 15 16 18 0 0 0 0 0 
후 위치: 8 6 3
후 배수: 20 24 20

전 위치: 8 6 3
전 배수: 20 24 20
1 2 3 4 5 6 8 9 10 12 15 16 18 20 0 0 0 0 
후 위치: 9 6 4
후 배수: 24 24 25

전 위치: 9 6 4
전 배수: 24 24 25
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 0 0 0 
후 위치: 10 7 4
후 배수: 30 27 25

전 위치: 10 7 4
전 배수: 30 27 25
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 0 0 
후 위치: 10 7 5
후 배수: 30 27 30

전 위치: 10 7 5
전 배수: 30 27 30
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 0 
후 위치: 10 8 5
후 배수: 30 30 30

전 위치: 10 8 5
전 배수: 30 30 30
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 
후 위치: 11 9 6
후 배수: 32 36 40