- 성능 요약
- 구분
- Answer Code1(2022.02.20)
- Answer1 - 문제 풀이
- Answer Code2(2022.02.24)
- Answer2 - 문제 풀이
- Review
- Reference
성능 요약
-
메모리: 67.2 MB, 시간: 8.99 ms - Answer Code1(2022.02.20)
-
메모리: 72.9 MB, 시간: 0.09 ms - Answer Code2(2022.02.23)
구분
- 코딩테스트연습 > 2022 KAKAO BLIND RECRUITMENT
Answer Code1(2022.02.20)
import java.util.*;
class Solution {
public int solution(int n, int k) {
int answer = 0;
String temp = "";
//N진법 변환
while(n != 0) {
temp = n % k + temp;
n /= k;
}
String [] arr = temp.split("0");
for(String str : arr) {
if(str.equals("")) {
continue;
}
long num = Long.parseLong(str);
if(isPrime(num)) {
answer++;
}
}
return answer;
}
// 소수 확인 메서드
public boolean isPrime(long decimal) {
if(decimal < 2)
return false;
for(int i = 2; i <= Math.sqrt(decimal); i++) {
if(decimal % i == 0) {
return false;
}
}
return true;
}
}
Answer1 - 문제 풀이
-
소수 판별 알고리즘 문제였다.
-
처음에 문제에 대한 설명을 보고 도무지 이해가 안되어서 가만히 생각해봤는데,
0을 기준으로 분해시켜서 개수를 구하면 되는 문제였다. -
[1] N진법 로직으로 구현한다.
- N진법 변환 로직은 While문을 사용하여, N을 K로 나눈 나머지를 계속 앞에 붙여나간다.
-
[2] N진법으로 푼 문자열을
0을 기준으로 Split 한다.-
주의 1) 1001 처럼 가운데 0이 있는 상태로 분해할 경우 1, “”, 1이 반환이 된다. 빈칸을 숫자로 변환하면 오류가 생기니 이런 경우를 제외해야 한다.
-
주의 2) 변환할 때 숫자를 Long 타입으로 바꿔야한다. 최대 100만이라는 숫자를 N진법으로 변환하면 엄청난 길의 숫자가 나열되고, int의 범위를 넘어서는 숫자가 생성되기 때문이다.
-
-
소수를 판별할 때는 에라토네스 체를 사용하는 걸 권장한다. 권장한 이유는 연산을 최대한 많이 줄이면서 소수인지 판별이 가능하기 때문이다.
Answer Code2(2022.02.24)
class Solution {
public int solution(int n, int k) {
int ans = 0;
String temp[] = Integer.toString(n, k).split("0");
Loop : for(String t : temp) {
if(t.length() == 0) continue;
long a = Long.parseLong(t);
if(a == 1) continue;
for(int i=2; i<=Math.sqrt(a); i++)
if(a%i == 0) continue Loop;
ans++;
}
return ans;
}
}
Answer2 - 문제 풀이
-
두 번째 풀이는 좋아요 수가 많은 답안인데, 정말 깔끔한 풀이였다.
-
10진수 -> k진수로 변경은
String.valueOf(바꾸려는 숫자(10진수), 바꾸려는 k진법)으로 간단하게 구현 가능하는 것을 구글링을 통해 알게 되었다. -
Prime() 메서드를 단 세줄로 작성했다는 점에서 성능이 8배 가까이 개선되었다.
Review
- 문제를 푼다고 끝내지 말고, 더 나은 성능 개선을 위해 깔끔하면서 좋은 코드를 구현하려고 노력하자.