[cote] 기사단원의 무기

코딩테스트(level 1) - 기사단원의 무기

프로그래머스

 

진행과정1 : 시간초과

	int answer = 0;
	for (int i = 0; i < number; i++) {
            int temp = 0;
            for (int j = 1; j < i+2; j++) {
                if ((i + 1) % j == 0) {
                    temp += 1;
                }
            }
            if (temp > limit) {
                answer += power;
            } else {
                answer += temp;
            }
        }
        return answer;

 

시간초과가 떴다.

 

진행과정2 : 비효율적인 for문 개선

n의 약수의 갯수가 limit을 초과하면 power를 더해주는 식으로 진행했으므로 limit을 초과하고도 도는 횟수가 많아서 인걸로 판단하여 for문에 break 문을 걸었다. 예를들어 1부터 100까지 돌던 중 특정 n에서 limit을 초과하게 되면 즉시 그 루프를 중단하고 다음 루프로 넘어갈 수 있도록 만들었다.

	int answer = 0;
        for (int i = 1; i < number+1; i++) {
            int temp = 0;
            for (int j = 1; j < i+1; j++) {
                if (i % j == 0) {
                    temp += 1;
                }
                if (temp > limit) {
                    answer += power;
                    break;
                }
            }
            if (temp <= limit) {
                answer += temp;
            }
        }
        return answer;

단순히 for문의 비효율성 문제가 아닌 듯 싶었다 시간초과되는 test case는 줄었으나 여전히 시간초과가 발생했다.

 

진행과정3 : 약수를 구하는 알고리즘

약수를 구하는 과정에서 1부터 n까지 모두 탐색하기에 시간복잡도가 높아서라고 판단하였다. 

 

limit이 작은 수라고 착각하였다 만약 limit이 1000이 넘는 숫자라면 1001을 찾기 위해서 무의미한 루프를 계속 돌아야할 것이다.(그전에 루프가 끝난다면 좋겠지만 10000이라는 숫자를 확인한다면 현재 방법으로는 10000번을 모두 돌아야한다) 따라서 약수의 갯수를 미리 구해서 돌 가치가 있는 상황인지 판단하게 되면 그만큼 줄어든다고 생각했다.

 

 

"N의 약수를 구할 때는, 1부터 N의 제곱근 까지의 수만 0으로 나누어 떨어지는지 확인하면 된다!"

 

위 말은 100의 제곱근을 구할때 1부터 100의 제곱근인 10까지만 나누어 떨어지는지 확인하고 1부터 10까지 나누어 떨어진 값으로 다시 나누어 확인을 하면 된다.

 

이를 통해 시간 복잡도가 O(√N)으로 줄어들 수 있다.

 

코드 변경 시작.

 

        int answer = 0;
        for (int i = 1; i < number+1; i++) {
            List<Integer> listOfDivisor = new ArrayList<>();
            int sqrt = (int) Math.sqrt(i);
            int temp = i;
            // 제곱근까지의 약수확인
            IntStream.range(1, sqrt+1)
                    .filter(x -> temp % x == 0)
                    .forEach(listOfDivisor::add);
            // 리스트의 내용물로 다시 i를 나누어 저장
            for (int j = 0; j < listOfDivisor.size(); j++) {
                int divisor = temp / listOfDivisor.get(j);
                if (!(listOfDivisor.contains(divisor))) {
                    listOfDivisor.add(divisor);
                }
            }
            if (listOfDivisor.size() > limit) {
                answer += power;
            } else {
                answer += listOfDivisor.size();
            }
        }
        return answer;

성공

 

개선

성공 확인한 후 다른 사람들과의 코드 비교하였는데 너무 어렵게 풀었다는 사실을 확인했다. 제곱근 확인을 위해 Math.sqrt()를 사용할 필요도 없다는 것을 확인하여 다음과 같이 개선하였다.

 

        int answer = 0;
        // 각 기사단 약수용 어레이
        int[] count = new int[number + 1]; // 0 사용하지 않음.

        for (int i = 1; i <= number; i++) {            // --- [1]
            for (int j = 1; j * j <= i; j++) {         // --- [2]
                if (j * j == i) count[i]++;
                else if (i % j == 0) count[i] += 2;
            }
        }
        for (int i = 1; i < count.length; i++) {       // --- [3]
            if (count[i] > limit) {
                answer += power;
            } else {
                answer += count[i];
            }
        }
        return answer;

 

[1] - 첫번째 포문 i는 1번 기사부터 n번째 기사까지 도는 것을 말한다.

[2] - 내부 포문은 i번째 기사의 약수 갯수를 세주는 역할이다. j * j 제곱근이 정확히 i와 일치하면 1을 더해주고 아닌 경우는 쌍으로 존재하므로 2를 더해준다.

[3] - 각 i번째 기사까지 limit을 초과한 경우 power를 대신 더해준다.

 

 

list를 사용하는 과정이 [2]포문 하나로 압축된다.

 

 

 

 

참고 자료

 

[JAVA] 약수 갯수 구하기

[Java] 약수의 개수 구하기