728x90
이해하기
자신있던 소수 찾기 문제! 였지만 첫 번째 풀이에서 시간 초과 (런타임 에러) 를 마주했다 ㅋㅋ...
class Solution {
public int solution(int n) {
int answer = 0;
for (int i = 2; i <= n; i++) {
if (isPrime(i)) {
answer++;
}
}
return answer;
}
public boolean isPrime(int n) {
if (n == 2) {
return true;
}
for (int i = 2; i <= n / 2; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
}
첫 번째 접근 방법은 아래와 같았다.
- 2부터 n까지 for문을 돌린다.
- i가 소수인지 확인한다.
- 2는 소수이니 바로 return true해준다.
- 아니라면 밑의 for문을 돌린다.
- 2부터 n/2로 n을 나눠보면서, 하나라도 나누어 떨어지는 수가 있다면 false를 반환한다.
- 아니라면 true를 반환한다.
여기서 시간 초과가 났던 부분은 ' 2부터 n/2로 n을 나눠본다.'였던 것 같다.
고민하다가 전에 다른 문제에서 Math.sqrt(n)까지만 소수 확인을 했던 것이 떠올라서 두 번째 풀이에 적용해보았다.
문제풀이
class Solution {
public int solution(int n) {
int answer = 0;
for (int i = 2; i <= n; i++) {
if (isPrime(i)) {
answer++;
}
}
return answer;
}
public boolean isPrime(int n) {
if (n == 2) {
return true;
}
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
}
요거 하나만 고쳐주었는데도 바로 통과! 앞으로 소수 관련 문제가 나오면 Math.sqrt(n)까지만 확인해보도록 해야지...!
'JAVA > Coding Test Study' 카테고리의 다른 글
[Lv.1] 키패드 누르기 : Java (0) | 2024.04.02 |
---|---|
[Lv.1] 모의고사 : Java (1) | 2024.04.01 |
[Lv.2] 카펫 : Java (0) | 2024.04.01 |
[Lv.3] 여행경로 : Java (0) | 2024.03.27 |
[Lv.2] 수식 최대화 : Java (2) | 2024.03.27 |