본문 바로가기
JAVA/Coding Test Study

[Lv.1] 소수 찾기 : Java

by ♡˖GYURI˖♡ 2024. 4. 1.
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;
    }
}

 

첫 번째 접근 방법은 아래와 같았다.

  1. 2부터 n까지 for문을 돌린다.
  2. 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