문제 요약
1번부터 number까지 번호를 가진 기사에게 공격력을 지닌 무기를 나눠줄 예정이다.
각 기사는 자신의 번호의 약수 개수에 해당하는 공격력을 지닌 무기를 구매할 것이지만, 이웃나라와의 규약에 의해 제한된 수치(limit)를 넘어면 정해진 수치(power)의 무기를 구매해야 한다.
공격력 1당 1Kg의 무게를 가지며, 각 기사가 구매할 무개의 전체 무게(result)를 구해보자
[ 예시 ]
| number | limit | power | result |
|---|---|---|---|
| 5 | 3 | 2 | 10 |
| 10 | 3 | 2 | 21 |
[ 제약 조건 ]
[ 프로그래머스 ]
풀이
- 구해진 약수들은 중복이 있을 수 있기 때문에(
5*5같은), 중복을 걸러주는Set을 사용하였다.
1) 1부터 기사의 고유번호(x)의 제곱근만큼 반복한다.
-x % i == 0: 약수임을 의미
또한,x/i값을 이용하여 짝이 되는 값을 구할 수 있다. 이 짝이 되는 값 역시 x의 약수가 된다.
-x % i != 0: 약수가 아님을 의미
2) 약수 값과 해당 약수의 짝이 되는 값을set에 넣어 중복을 거른다.
3)set.size()를 통해 약수의 개수를 구하고limit이하면,set.size()반환
그렇지 않다면,power를 반환한다.
Code
import java.math.*;
import java.util.*;
class Solution {
public int solution(int number, int limit, int power) {
int answer = 0;
for(int i=1;i<=number;i++) {
answer+=getPower(power,limit,i);
}
return answer;
}
private static int getPower(int power, int limit, int x) {
Set<Integer> set = new HashSet<>();
for(int i=1;i<=Math.sqrt(x);i++) {
if (x%i == 0) {
set.add(i);
set.add(x/i);
}
}
if (set.size() > limit)
return power;
return set.size();
}
}시도
1) 원초적인 약수 구하기
1 ~ N까지 반복문을 열어 %==0인 값들을 저장하는 식을 생각했지만, 이중 for문으로 이 날 것이니 number≤100,000에서 시간 초과가 날 것이다.
2) 핵심은 약수 구하기의 시간을 줄이는 것
약수가 되는 수가 있으면, 그 짝이 되는 수가 분명히 존재한다. 예를 들어, 100의 약수로 2*50이나 10*10이 있듯, 굳이 100까지 가지않고 그 제곱근까지만 반복해도 모든 약수를 구할 수 있다.
앞선 10*10과 같이 중복되는 숫자의 곱이 있을 수 있기에 중복 허용을 하지 않는 자료구조 HashSet을 이용하면 성공이다.
느낀점
일전에는 계획을 짜기 전 일단 코드부터 작성해 문제 풀이에 많은 시간이 소요됨과 더불어 문제의 의도를 파악하지 못했다. 문제 풀이를 적으면서 생각하니 확실히 풀이 시간에도 수정 시간에도 적은 소요가 소모되고 있다.
