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

카테고리

완전 탐색

나만의 카테고리

소수 찾기, 숫자 조합해서 만들기

문제 링크

http://programmers.co.kr/learn/courses/30/lessons/42839?language=java

요점

• 에라토스테네스의 체를 통해 소수 찾기를 진행해야한다
• 숫자를 쪼개서 전체 숫자를 만드는 것은 역으로 쪼개진 숫자를 타겟이 모두 포함하는지를 확인하는 것이 편하다

참고 지식

• 에라토스테네스의 체
• Arrays.sort 메소드
• List에서 remove 시에는 처음 찾아진 요소 제거
• Boolean 초기값

풀이 (Java)

import java.util.*;

class Solution {
    public int solution(String numbers) {
        int answer = 0;

        String[] array = numbers.split("");

        // 소수를 찾을 최대 값을 구하기 위해 전체를 내림차순으로 정렬 
        Arrays.sort(array, Collections.reverseOrder());

        String maxNumberStr = "";
        // 정렬된 숫자를 하나의 string으로 만든다면 최대의 숫자
        for (String eachNumber : array) {
            maxNumberStr = maxNumberStr + eachNumber;
        }

        int maxNumber = Integer.parseInt(maxNumberStr);

        boolean prime[] = new boolean[maxNumber + 1];

        prime[0] = prime[1] = true; // boolean의 초기값이 false이므로 true로 활용

        prime = getAllPrime(maxNumber, prime);

        // 구한 소수 전체와 타겟 숫자를 비교
        for (int i = 2; i <= maxNumber; i++) {
            if (!prime[i]) {
                String temp[] = new String[8];
                String primeString = Integer.toString(i);

                String[] splitPrime = primeString.split("");
                ArrayList<String> splitPrimeList = new ArrayList<>(Arrays.asList(splitPrime));

                for (String str : array) {
                    splitPrimeList.remove(str);
                }

                if (splitPrimeList.size() == 0) {
                    answer++;
                }

            }
        }

        return answer;
    }

    public static boolean[] getAllPrime(int num, boolean prime[]){
        for (int i = 2; i < Math.sqrt(num); i++) {
            if (!prime[i]) {
                for (int j = i * i; j <= num; j += i) {
                    prime[j] = true;
                }
            }
        }

        return prime;
    }
}

급하게 푸느라 변수명이 중구난방인거는 감안해주세요. 에라토스테네스의 체는 코드 자체를 기억해 두는 것도 좋은 방법일 것 같습니다. 온라인 코딩 테스트 시에는 바로 검색해서 찾아내도 괜찮긴 하지만요 ㅎㅎ

이 문제는 효율성은 따지지 않으므로 리스트고 배열이고 그냥 순회하도록 짰습니다.

 
 

알고리즘 초보가 정리한 글입니다 더 좋은 방법이나 코드에 대한 코멘트 언제나 환영합니다!