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

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

class Solution {
	public int solution(int number, int limit, int power) {
		// 1~number 번호
		// 기사번호의 약수 개수에 해당하는 공격력을 가진 무기 구매
		// 공격력 제한수치, 제한수치보다 큰 공격력 기사는 협약 기관 공격력
		// 초과하면 power 수치로 사용
		// 1. 기사 단원 번호 별 약수개수 배열 생성
		// 2. 배열의 값이 limit을 넘으면 power로 대체
		// 3. 철 무게 (배열의 값 모두 합)

		int[] counts = new int[number + 1];

		for (int i = 1; i <= number; i++) {
			int count = measure(i);

			if (count > limit) {
				counts[i] = power;
			} else {
				counts[i] = count;
			}
		}

		int sum = 0;

		for (int i = 1; i <= number; i++) {
			sum += counts[i];
		}

		return sum;
	}

	private int measure(int n) {
		int count = 0;
		for (int i = 1; i <= Math.sqrt(n); i++) {
			if (n % i == 0) {
				if (i * i == n) {
					count++;
				} else {
					count += 2;
				}
			}
		}
		return count;
	}
}

• 기사 번호마다 약수의 수를 저장하는 배열을 생성
• 만약 약수의 수가 limit을 초과한다면 power로 대체
• 약수의 수 구하기
  • 제곱근 까지만 나눠서 구해주면 됨
    ex) 10 -> 1 2 5 10 -> 2x5와 5x2는 같으니깐, 2개로 증가 시켜주기
  • 만일 9 -> 1 3 9 에서 -> 3의 경우에는 3x3이 두개가 되니깐 이런 경우는 1개만 증가
  • 시간 복잡도가 반으로 줄어들 수 있음
  • 출처 : GPT