[프로그래머스 2단계] 알고리즘 19. 소수 찾기

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 19. 소수 찾기

numberOfPrime 메소드는 정수 n을 매개변수로 입력받습니다.1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하도록 numberOfPrime 메소드를 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)

10을 입력받았다면, 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
5를 입력받았다면, 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

class NumOfPrime {

    int numberOfPrime(int n) {

        int result = 0;

        // 함수를 완성하세요.

        return result;

    }

    public static void main(String[] args) {

        NumOfPrime prime = new NumOfPrime();

        System.out.println( prime.numberOfPrime(10) );

    }

}

풀이 : 

풀이에 앞서 이제부터는 모든 문제를 최대한 자바로 풀 것임을 알린다. 다만 프로그래머스에서 아예 자바를 지원하지 않는 문제에 대해서는 c++ -> 파이썬 -> 자바스크립트 순으로 문제를 풀 예정이다. 이번에도 역시 함수형으로 풀어볼 생각이다. 함수형으로 문제를 풀 때는 입력과 출력에 따른 문제 해결 방법을 먼저 생각하는 것이 좋다. 이 문제의 경우 프로그래밍 상 입력은 N이지만 1~N 사이의 수를 검사하는 것이니까 정확한 입력은 1~N 사이의 수들이다.(스트림!) 그러나 1을 검사할 필요는 없다. 왜냐하면 제일 작은 소수는 2이기 때문이다! 그리고 그 수들이 소수인지 판단하고 소수가 맞는 수들의 개수를 반환하면 된다. 깔끔하게 다시 정리하자.

1. 입력은 2~N사이의 수들이다.
   -> 이들은 스트림으로 표현할 수 있다!
2. 2~N 사이의 수들 중 소수인 것들만 찾는다.
   -> 소수인것들을 찾는 함수는 isPrime이다!
3. 그 개수를 반환한다.

코드로 옮기면 다음과 같다.

int numberOfPrime(int n) {

    int result = (int) IntStream.rangeClosed(2, n) //2~N 사이의 수를 스트림으로

.filter(i -> isPrime(i))    //그 스트림 요소중 isPrime이 true인것만 필터

.count();                //그 요소들의 개수(long -> int)

        return result;

}

그 다음 isPrime이라는 함수를 생각해보기 전에 먼저 소수라는 것이 어떤 것인지 알아보자.

"소수란 어떤 수 N에 대해서 1과 본인 N 외에 그 사이의 수들로 나누어 떨어지지 않는 수이다."

그렇다면 함수적으로 어떻게 풀지 고민해보자. 일단 입력을 받은 n에 대해서 2부터 n-1까지 나누어 떨어지면 안된다. 그렇다면 이것도 위와 같다. 프로그래밍 상 입력은 n이지만 실제 입력은 2~n-1까지의 수들이다.(스트림!) 그리고 n은 2~n-1 사이의 수들로 단 한개라도 나누어 떨어지면 안된다. 이 문제도 다시 정리하자.

1. 입력은 2~n-1 사이의 수들이다. -> 스트림으로 표현할 수 있다.
2. 단 한개라도 그들은 n에 대해서 나누어 떨어지면 안된다.

이 문제의 해결 방식은 n이 모두 스트림 요소들을 나누어 떨어지지 않는지 검사하는 것이 포인트이다! 나같은 경우 먼저 이렇게 풀었었다.

public static boolean isPrime(int n){

return IntStream.range(2, n)                        //2~n-1까지 스트림 반환

.mapToObj(i -> n % i != 0)         //n이 요소들로 나누어 떨어지지 않는다면 true로 매핑

.reduce(true, (a, b) -> a && b); //요소들이 모두 true를 반환한다면 그 수는 소수이다.

}

mapToObj는 스트림 요소를 람다식이 반환하는 데이터 타입으로 바꿔준다. 여기에서는 (i%2 != 0) 이라는 조건식을 써줌으로써 Boolean 요소로 매핑하였다. 그 후 커스텀 집계 함수인 reduce를 이용하여 초기값을 true로 왼쪽에서부터 요소들을 && 연산자로 합쳐주었다. 만약 나누어 떨어지지 않는 수들은 true로 바뀔 것이고 모두 true를 반환한다면 그 수는 소수일 것이다. 이 문제를 푸는데 더 간단하게 푸는 방법이 있다.

return IntStream.range(2, n)

.allMatch(i -> n % i != 0);

바로 allMatch 함수를 이용하는 것이다. 이 함수는 스트림 요소들이 주어진 조건에 모두 부합하는지 검사해주는 함수이다. 이렇게 어떤 수 N이 소수인지 아닌지 판단하는 함수를 작성할 수 있다. 다음은 내가 작성한 코드 전문이다.

import java.util.stream.*;

class NumOfPrime {

public static boolean isPrime(int n){

return IntStream.range(2, n)

.allMatch(i -> n % i != 0);

}

    int numberOfPrime(int n) {

        int result = (int) IntStream.rangeClosed(2, n)

.filter(i -> isPrime(i))

.count();

        return result;

    }

    public static void main(String[] args) {

        NumOfPrime prime = new NumOfPrime();

        System.out.println( prime.numberOfPrime(10) );

    }

}