[프로그래머스] 소수 찾기 Java

programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

 

문제 요약

문자열 numbers를 받는다. numbers의 각 자리 값은 0~9 이다. 이 값 들의 자리수 조합으로 만들 수 있는 소수의 개수를 반환하는 함수를 만들어야 한다.

 

문제 풀이

 이 문제는 완전 탐색 + DFS로 풀었다. 이 전과 같이 최대한 모던 자바로 풀려고 노력했다. 문제 자체는 어렵지 않았으나 모던자바를 적용하는데서 시간을 많이 빼앗겼다.

 

 우선 IntStream을 이용해서 문자열로 받은 숫자를 int 배열로 매핑했다. 그리고 숫자 조각들의 조합을 담을 HashSet을 선언하고 DFS로 나올 수 있는 조합들을 찾아서 Set에 채워넣었다. 마지막으로 소수인지 아닌지 반환하는 Predicate인 isPrime 함수를 만들고 필터링을 이용해서 Set의 값 들을 필터링하고 count() 로 개수를 반환했다.

 

 아직도 StreamAPI를 제대로 사용한다는 느낌은 받지 못한다. 앞으로 계속 공부하며 문제를 풀어나가야겠다. 

 

나의 코드

import java.util.*;
import java.util.stream.IntStream;

class 소수_찾기 {
    Set<Integer> comb = new HashSet<>();    //  가능한 조합들을 중복없이 저장할 HashSet

    public int solution(String numbers) {
        /* 문자열로 받은 종이를 종이 조각 int 배열로 매핑 */
        int[] piece = IntStream.rangeClosed(0, numbers.length() - 1) 
                .map(i -> numbers.charAt(i) - '0')
                .toArray();

        // dfs 함수를 이용해 가능한 종이조각 조합을 찾아서 set 에 넣기
        boolean[] visited = new boolean[piece.length];
        for (int i = 0; i < piece.length; ++i) {
            visited[i] = true;
            findComb(piece[i], piece, visited);
            visited[i] = false;
        }

        // 조합 중 소수의 개수 반환
        return (int) comb.stream()
                .filter(this::isPrime)
                .count();
    }

    /* 조합 찾기 dfs 함수 */
    public void findComb(int result, int[] piece, boolean[] visited) {
        comb.add(result);
        for (int i = 0; i < piece.length; ++i) {
            if (!visited[i]) {
                visited[i] = true;
                findComb(result * 10 + piece[i], piece, visited);
                visited[i] = false;
            }
        }
    }

    /* 소수 Predicate */
    public Boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i <= (int) Math.sqrt(n); ++i)
            if (n % i == 0) return false;
        return true;
    }
}