이번에 약분을 구하는 문제를 풀어보면서 배운 내용을 정리해보려고 한다!
요즘 따로 정리를 너무 안해서 다시 1일 2블로그(알고리즘, 안드로이드)를 실천하자!!
소수를 구하는 알고리즘
소수를 구하는 알고리즘을 알기 위해서는 소수가 무엇인지 스스로 제대로 정의하고 시작해야한다
소수는 1~n까지 숫자 중 n % i == 0인게 n과 1밖에 없는 수를 의미한다
ex) 3,7등의 숫자를 의미한다 여기서 1은 소수에서 제외고 2부터 시작한다
소수를 판별하기 때문에 참,거짓을 반환값으로 했다.
여기서 전부를 돌수도 있지만 8의 경우 2에서 나눠지고, 9의 경우 3에서 나눠진다
즉 Math.sqrt(n), 제곱근만큼만 가도 소수인지 확인이 가능하므로 꼭 n만큼 돌지 않아도 log(n)번으로도 소수 확인이 가능하다!
private boolean isPrime(int n) {
boolean isCheck = true;
for(int i = 0; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
isCheck = false;
break;
}
}
return false;
}특정 수의 약분 개수를 구하는 알고리즘
8의 경우 1,2,4,8 총 4개의 수로 나머지 0으로 나눌 수 있다.
이렇게 나머지가 0으로 나눠지는 숫자가 바로 약분 숫자다!
8의 경우 1x8 2x4 4x2 1x8로 변환이 가능하다 -> 각 2번씩 나옴
9같은 제곱근의 경우 1x9 3x3 9x1 처럼 중간 제곱근이 1개 나오고 9와 1이 2개 씩 나온다
이걸 생각하고 코드를 작성하면 된다!!
private int abbreviationCount(int n) {
int cnt = 0;
for (int i = 0; i*i<= n; i++) {
if (i*i == n) cnt++;
else if (n % i == 0) cnt+=2;
}
return cnt;
}여러 수의 약분 개수를 구하는 알고리즘
저 위에 알고리즘을 이용해서 구해도 여러 수의 약분을 구할 수 있다
하지만 이번에 문제를 풀면서 배운 알고리즘을 사용해보려고한다!
지금까지는 나누면서 접근했지만 여기서는 곱하기를 이용해 접근한다!
4라고 하면 이것과 관련있는 배수들을 찾아서 +1씩 해주는 것이다
int dp[] = new int[e+1];
for (int i = 1; i<=e; i++) {
for(int j = 1; j <= e/i; j++) {
dp[i*j]++;
}
}코딩문제-억억단을 외우자
알고리즘 풀이
단순하게 소수와 약분개수를 이용해서 풀었지만 시간초과가 나버렸다..
소수를 구하는 함수까지 돌려버리면 시간초과가 날 수 밖에 없는 문제였다
이 문제의 경우 e부터 가장 약분개수가 많은 인덱스를 1~e사이의 배열들에 저장하면 된다
이게 핵심인 문제였고 나는 dp를 생각하지 않고 풀어서 시간초과가 났었다!!
코드
레벨3 문제인데 코드가 짧아서 레벨1 같아보이네...
class Solution {
public int[] solution(int e, int[] starts) {
int[] answer = new int[starts.length];
int [] dp = new int[e + 1];
for (int i = 1; i<= e; i++) {
for (int j = 1; j <= e/i; j++) {
dp[i*j]++;
}
}
int []cp = new int[e+1];
// 최대 idx 넣는 곳!
// 이제 1~e까지 최댓값을 지정해두기!
cp[e] = e;
int temp = dp[e];
for (int i = e-1; i>=1; i--) {
if (temp <= dp[i]) {
temp = dp[i];
cp[i] = i;
} else {
cp[i] = cp[i+1];
}
}
for (int i = 0; i<starts.length; i++) {
answer[i] = cp[starts[i]];
}
return answer;
}
}