[프로그래머스/Lv.1] 기사단원의 무기 - Java

📌 문제

프로그래머스

📌 처음 작성한 코드 - 오답

이번 문제는 1부터 number까지 각 숫자의 약수의 개수를 구한 후, limit을 초과한다면 그 수를 power로 수정해 약수의 개수의 합을 반환하는 문제이다. 처음 작성한 코드는 기존 테스트 케이스에서는 통과했지만 제출을 하니 시간초과로 오답처리 되었다. 찾아보니 약수의 개수를 세는 부분에서 시간 초과가 난 것이었다. 내가 작성한 코드처럼 약수를 구할 때 1부터 number까지 돌며 모든 경우를 탐색한다면 O(N)의 시간복잡도를 가지게 된다. 만약 제한사항대로 number가 최대 100,000이라면 시간초과가 날 수밖에 없다. 이를 해결하려면 반복문을 제곱근까지만 돌리면 된다는 사실을 기억하자.

import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {
        int[] count = new int[number];
        int index = 0;
        
        for (int i = 1; i <= number; i++) {
            for (int j = 1; j <= i; j++) {
                if (i % j == 0) count[index]++;
            }
            index++;
        }
        
        int answer = 0;
        for (int i = 0; i < number; i++) {
            if (count[i] > limit) count[i] = power;
            answer += count[i];
        }
        
        return answer;
    }
}

📌 풀이

다시 제대로 된 코드로 풀이를 기록해보겠다. 먼저 약수의 개수를 기록하는 int형 배열 count와 count의 인덱스 역할을 하는 int 변수 index를 선언한다.

int[] count = new int[number];
int index = 0;

 

이 부분에서 시간초과가 났는데, 두 번째 반목문을 i의 제곱근까지만 돌도록 수정하였다. 예를 들어 number가 16이라면 16의 약수는 1, 2, 4, 8, 16이다. 16의 제곱근인 4까지만 돌면 되는 이유는 1 - 16, 2 - 8 과 같이 제곱근을 제외하고는 쌍을 이루기 때문이다. 따라서 i / j == 0, 즉 j가 i의 제곱근일 경우, count를 1 증가 시키고, 그게 아니라면 어차피 쌍을 이루므로 count를 2 증가시킨다.

for (int i = 1; i <= number; i++) {
    for (int j = 1; j <= Math.sqrt(i); j++) {
        if (i % j == 0) {
            if (i / j == j) count[index]++;
            else count[index]+=2;
        }
    }
    index++;
}

 

그리고나서 count를 돌며 약수의 개수가 limit을 초과한다면 power로 바꾸고, 초과하지 않는다면 그대로 둔다. 최종적으로 나온 값을 answer에 모두 더해 반환하면 끝!

int answer = 0;
for (int i = 0; i < count.length; i++) {
    count[i] = count[i] > limit ? power : count[i];
    answer += count[i];
}

📌 전체 코드

import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {
        int[] count = new int[number];
        int index = 0;

        for (int i = 1; i <= number; i++) {
            for (int j = 1; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    if (i / j == j) count[index]++;
                    else count[index]+=2;
                }
            }
            index++;
        }
        
        int answer = 0;
        for (int i = 0; i < count.length; i++) {
            count[i] = count[i] > limit ? power : count[i];
            answer += count[i];
        }
        
        return answer;
    }
}