프로그래머스 :: 소수만들기

https://school.programmers.co.kr/learn/courses/30/lessons/12977

프로그래머스

 

1. 주어진 숫자중에서 3개의 숫자를 골라야함 -> 조합으로 구현해볼까?

2. 구해진 조합의 합을 구해 배열에 넣어줌

3. 합의 배열을 가지고 각 원소가 소수인지 판단하여 count를 해줌

4. count 수 반환

 

---

이렇게 간단하게 생각하고 예전에 공부했던 것들을 꺼내 만들어보려고하니 점점 산으로 가는 것 같았지만.. 어쨌든 풀긴 풀었음

 

일단

1. n개 숫자중에서 3개 뽑기

2. 조합의 합을 sumList 에 넣어준다.

// 조합의 합을 저장해둘 sumList
static List<Integer> sumList = new ArrayList<>();

public static void combination(int[] nums, boolean[] visited, int depth, int n, int r) {
        if (r == 0) {
            print(nums, visited, n);
            return;
        }
        if (depth == n) {
            return;
        }
        visited[depth] = true;
        combination(nums, visited, depth + 1, n, r - 1);

        visited[depth] = false;
        combination(nums, visited, depth + 1, n, r);
 }


 public static void print(int[] nums, boolean[] visited, int n) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                sum += nums[i];		// 여기서 각 조합의 합을 구하고
            }
        }
        sumList.add(sum);		// sumList에 add
 }

 

3. sumList에 있는 원소들이 소수인지 판단하고 소수이면 1을, 아니면 0을 반환한다.

  public static int isPrime(int n) {
        if (n < 2) {
            return 0;
        }

        if ( n == 2) {
            return 1;
        }

        for (int i = 2; i < n ; i++) {
            if ( n % i == 0) {
                return 0;
            }
        }
        return 1;
    }

 

4. main 메소드 쪽에서 isPrime의 반환값을 더해주면 끝

 for (int sum : sumList) {
            answer += isPrime(sum);
 }
 return answer;

 

 

이렇게하면 통과는 함 but, 뒤쪽 테스트에서 시간이 조금씩 길어지는 것을 확인

 

시간을 줄여볼 방법을 생각하다가, 소수 판별 시 모든 숫자를 순회할 필요 없다는 것이 기억났다!

 

public static int isPrime(int n) {
        if (n < 2) {
            return 0;
        }

        for (int i = 2; i <= Math.sqrt(n) ; i++) {
            if ( n % i == 0) {
                return 0;
            }
        }
        return 1;
    }

 

이렇게 for loop의 범위를 제곱근을 사용해 줄여주면 ~!

 

 

 

개선 완?료?