[프로그래머스] 기사단원의 무기

---

프로그래머스 Lv1 - 기사단원의 무기 문제

주어진 number를 순회하며 해당 number의 약수의 개수를 가지는 리스트에 추가하고, 리스트를 순회하며 해당 개수(공격력)이 limit를 초과할 경우는 power를 더하고, 아닐 경우 해당 개수를 더해주어 무기를 모두 만들기 위해 필요한 철의 무게를 리턴하도록 풀이했다.

약수 알고리즘의 경우 제곱근을 사용하지 않고 그냥 순회하려고 했지만 문제 제한 사항 중

• 1 ≤ number ≤ 100,000
  조건이 신경쓰여 더 최적화된 약수 알고리즘이 있을까 서칭을하여 적용했다.
  약수 알고리즘의 경우 코딩 테스트에 전반적으로 많이 쓰이는 것 같아 익혀놓으면 좋을 것 같다.

약수 알고리즘 참조

TemplarWeapon.java

package com.example.Programmers.Lv1;

import java.util.ArrayList;
import java.util.List;

/**
 * 프로그래머스 Lv1 - 기사단원의 무기
 */
public class TemplarWeapon {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        List<Integer> cntList = new ArrayList<>();
        for (int i = 1; i <= number; i++) {
            int sqrt = (int) Math.sqrt(i);
            int cnt = 0;
            for (int j = 1; j <= sqrt; j++) {
                if (i % j == 0) { // 약수 중 작은 수 저장
                    cnt++;
                    if (i / j != j) { // 약수 중 큰 수 저장
                        cnt++;
                    }
                }
            }
            cntList.add(cnt);
        }

        for (Integer cnt : cntList) {
            answer += cnt > limit ? power : cnt;
        }
        return answer;
    }
}

TemplarWeaponTest.java

package com.example.Programmers.Lv1;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class TemplarWeaponTest {
    @Test
    public void testTemplarWeapon() {

        TemplarWeapon tw = new TemplarWeapon();
        int result1 = tw.solution(5, 3, 2);
        int result2 = tw.solution(10, 3, 2);

        assertEquals(10, result1);
        assertEquals(21, result2);
    }
}