프로그래머스: 숫자의 표현

문제

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

코드

삽질 코드

public int solution(int n) {
    int answer = 0;
    int[] sumArray = new int[n + 1];

    Queue<Integer> queue = initQueue(n);

    int sum = 0;
    for (int i = 1; i < n + 1; i++) {
        sum += i;
        sumArray[i] = sum;

        if (sum == n) {
            ++answer;

            int nextValue = i+1;

            while (!queue.isEmpty()) {
                int sumValue = sumArray[queue.peek()];

                if (nextValue <= sumValue) {
                    i = queue.peek();
                    sum = 0;
                    break;
                }

                queue.poll();
            }
        } else if (sum > n) {
            int value = sum - n;

            while (!queue.isEmpty()) {
                int sumValue = sumArray[queue.peek()];

                if (value <= sumValue) {
                    i = queue.poll();
                    sum = 0;
                    break;
                }

                queue.poll();
            }
        }
    }

    return answer;
}

합계를 저장 할 array와 배열의 index를 저장 할 queue를 생성하고 queue에 index를 순서대로 할당해놓는다.
i를 증가 시키면서 sum을 저장하고 sum == n 이 되면 answer을 증가시키고, 그 다음 index의 값을 구해서 그 다음 값 만큼 이전에 더한 값들을 빼고 뺀 값 다음 index부터 실행하기 위해 index를 queue에서 가져온다.
- 1 + 2 + 3 + 4 + 5 = 15 였으면 다음 값은 6 이므로 6을 만큼을 빼기 위해 1, 2 3을 뺀다.
sum이 n보다 크다면 sum에서 n을 뺀 값 만큼 더했던 값에서 빼고 뺀 값 다음 index부터 실행하기 위해 index를 queue에서 가져온다.
- 5 + 6 + 7 = 18 이므로 15를 뺀 3보다 크거나 같은 값을 앞에서부터 빼야되는데 5는 이미 3보다 크므로 5를 queue에서 poll해서 뺀다.
위를 반복해서 연속된 자연수의 개수를 구한다.
끝

숫자가 커지면 반복 할 때 효율성에서 걸릴까 싶어서 큐도쓰고 해봤는데 보기도 안좋고 속도도 안좋고 모든 면에서 안좋았다

정석 코드

public int solution(int n) {
    int answer = 0;

    for(int i = 1; i <= (n / 2) ; i++) {
        int sum = 0;
        int index = i;

        while (sum < n) {
            sum += index;
            ++index;
        }

        if (sum == n) {
            ++answer;
        }
    }

    return answer + 1;
}

n의 절반을 넘어가면 그 이상 더 해봤자 n을 넘어가므로 n / 2까지만 반복한다.
sum이 n 보다 작으면 반복해서 sum에 index를 증가시켜 가며 더한다.
sum이 n보다 작지 않아지면 빠져나와서 sum == n이 판단하고 같으면 answer을 증가시킨다.
마지막에 자기자신이 들어가므로 + 1을 하고 return한다.

결과

뻘짓 코드

정확성

번호	속도
테스트 1	통과 (1.02ms, 52.4MB)
테스트 2	통과 (2.01ms, 50.3MB)
테스트 3	통과 (1.64ms, 52.5MB)
테스트 4	통과 (1.83ms, 50.7MB)
테스트 5	통과 (1.13ms, 52.5MB)
테스트 6	통과 (0.95ms, 52.5MB)
테스트 7	통과 (1.68ms, 52.3MB)
테스트 8	통과 (1.41ms, 50.1MB)
테스트 9	통과 (0.93ms, 50MB)
테스트 10	통과 (2.25ms, 52.8MB)
테스트 11	통과 (2.15ms, 50.5MB)
테스트 12	통과 (1.78ms, 52.6MB)
테스트 13	통과 (1.86ms, 52MB)
테스트 14	통과 (1.68ms, 52.7MB)

효율성

번호	속도
테스트 1	통과 (9.68ms, 52.5MB)
테스트 2	통과 (6.16ms, 52.2MB)
테스트 3	통과 (7.96ms, 52MB)
테스트 4	통과 (7.72ms, 51MB)
테스트 5	통과 (8.29ms, 50.6MB)
테스트 6	통과 (10.67ms, 52.4MB)

정석 코드

정확성

번호	속도
테스트 1	통과 (0.77ms, 50.2MB)
테스트 2	통과 (0.94ms, 50.6MB)
테스트 3	통과 (0.81ms, 50.4MB)
테스트 4	통과 (0.86ms, 51MB)
테스트 5	통과 (0.80ms, 52.1MB)
테스트 6	통과 (0.77ms, 52.2MB)
테스트 7	통과 (0.90ms, 52.5MB)
테스트 8	통과 (0.84ms, 52.4MB)
테스트 9	통과 (0.69ms, 50.2MB)
테스트 10	통과 (0.87ms, 52.2MB)
테스트 11	통과 (0.91ms, 52.1MB)
테스트 12	통과 (0.89ms, 52.3MB)
테스트 13	통과 (0.79ms, 50.4MB)
테스트 14	통과 (0.84ms, 50.2MB)

효율성

번호	속도
테스트 1	통과 (1.48ms, 52.9MB)
테스트 2	통과 (1.12ms, 52.2MB)
테스트 3	통과 (1.21ms, 50.8MB)
테스트 4	통과 (1.28ms, 50MB)
테스트 5	통과 (1.52ms, 50.1MB)
테스트 6	통과 (1.50ms, 52.3MB)

테스트 케이스

assertEquals(4, test.solution(15));
assertEquals(2, test.solution(20));
assertEquals(4, test.solution(30));
assertEquals(2, test.solution(106));
assertEquals(2, test.solution(1567));
assertEquals(1, test.solution(16));
assertEquals(4, test.solution(782));
assertEquals(5, test.solution(10000));
assertEquals(12, test.solution(9999));
assertEquals(4, test.solution(7787));
assertEquals(8, test.solution(4578));
assertEquals(2, test.solution(1234));
assertEquals(1, test.solution(1));
assertEquals(2, test.solution(5));
assertEquals(3, test.solution(49));

P.S

주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수는 주어진 수의 홀수 약수의 개수와 같다.

이 문제의 최다 좋아요를 받은 코드는 위의 정수론 정리를 이용한 풀이가 있는데 정의의 출처를 찾지 못했다.
해당 정의를 가지고 푼 코드가 가장 짧고 가장 빠르게 실행된다.
한참 멀었구나 싶다.

프로그래머스: 숫자의 표현

문제

코드

삽질 코드

정석 코드

결과

뻘짓 코드

정석 코드

테스트 케이스

P.S

Junggu Ji