JAVA/Coding Test Study
[Lv.1] 소수 찾기 : Java
♡˖GYURI˖♡
2024. 4. 1. 19:26
728x90
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
이해하기
자신있던 소수 찾기 문제! 였지만 첫 번째 풀이에서 시간 초과 (런타임 에러) 를 마주했다 ㅋㅋ...
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)까지만 확인해보도록 해야지...!