프로그래머스 136798번
https://school.programmers.co.kr/learn/courses/30/lessons/136798

문제

---

생각하기

---

• 약수의 개수를구하는 문제이다.

  • 처음에 부르트포스로 돌렸는데, 역시나 시간초과가 발생했다.
  • 고민을 했지만, 최적화를 못하고 다른 분들의 코드를 본 후 문제를 해결 할 수 있었다.

동작

        for (int i = 1; i <= number; i++) {
            for (int j = 1; j <= number / i; j++) {
                count[i * j]++;
            }
        }

여기가 제일 중요한 부분인데 완전탐색을 하지 않고, 약수의 개수를 구하는 알고리즘을 통해서 최적화를 진행했다.

i값이 1부터 number까지 반복하면서j의 약수를 가지면 i * j의 값의 약수개수를 증가하도록 구현했다.

결과

코드

---

class Solution {
    public int solution(int number, int limit, int power) {
        int[] count = new int[number + 1];    
        for (int i = 1; i <= number; i++) {
            for (int j = 1; j <= number / i; j++) {
                if(count[i * j] > limit) continue;
                
                count[i * j]++;
            }
        }
        
        int answer = 0;
        for (int i = 1; i <= number; i++) {
            if (count[i] > limit) {
                answer += power;
            } else {
                answer += count[i];
            }
        }
        return answer;
    } // End of solution()
} // End of Solution class