2022.05.12 「LV2 소수 찾기」

여느 날처럼 코테 문제를 계속 풀고 있다. 
자료구조도 날 잡아서 한번 정리해야 되는데 시간이 좀 나질 않는다. 시간 배분 좀 잘해보자.
어제오늘 푼 것이 소수 찾기라는 완전 탐색 문제인데, 이건 소수라는 것이 결국 1과 자신만을 약수로 가지는 수를 말한다. 어떤 블로그에서 봤는데 결국 문제를 간소화하는 게 관건이라는데 그것을 보는 안목을 좀 길러야겠다.

 

소수 찾기

소수 : 1과 자기 자신만을 약수로 가지는 수

 

String 숫자 값을 받아 소수를 조합하는 개수를 구하는 문제이다.

import java.util.HashSet;
import java.util.Iterator;

class Solution {
    HashSet<Integer> numberSet = new HashSet<>();

    /**
     * 소수 확인 메서드
     * @param num 소수 확인 매개변수
     * @return boolean 논리 값 소수 여부
     */
    public boolean isPrimeNumber(int num) {
        if (num == 1 || num == 0) {
            return false;
        }

        int sqrt = (int) Math.sqrt(num);

        /**
         * 에라토스테네스의 체 
         * 배수 여부 판단
         */
        for (int i = 2; i <= sqrt; i++) {
            if (num % i == 0) {
                return false;
            }
        }

        return true;
    }

    /**
     * 조합 구하는 메서드
     * 재귀 함수 이용
     * @param combination 조합
     * @param otherNumbers 다른 숫자
     */
    public void recursive(String combination, String otherNumbers) {

        /**
         * 조합 추가
         */
        if (!combination.equals("")) {
            numberSet.add(Integer.parseInt(combination));
        }

        /**
         * 숫자를 더해 새로운 조합 추가
         */
        for (int i = 0; i < otherNumbers.length(); i++) {
            if (!combination.equals("")) {
                numberSet.add(Integer.valueOf(combination));
            }
            recursive(combination + otherNumbers.charAt(i), otherNumbers.substring(0, i) + otherNumbers.substring(i + 1));
        }
    }

    public int solution(String numbers) {
        int primeCount = 0;

        /**
         * 입력 받은 모든 조합 만들기
        */
        recursive("", numbers);

        Iterator<Integer> iterator = numberSet.iterator();

        while (iterator.hasNext()) {
            int number = iterator.next();

            if (isPrimeNumber(number)) {
                primeCount++;
            }
        }

        return primeCount;
    }
}

 

1. 소수를 구하기 위해 에라토스테네스의 체를 이용했다.

제곱근을 구해 그 개수를 구해 카운트를 얻어 반복문을 통해 소수 판별

참조 : https://firework-ham.tistory.com/8

[JAVA] 소수 구하는 알고리즘 : 에라토스테네스의 체

 

2. 가능한 모든 조합을 구하는 메서드

모든 조합을 Set에 넣었다. Set은 중복을 허용하지 않기 때문에 이 컬렉션을 사용했다.

 

3. 조합을 얻어 Iterator을 사용한 후 반복을 돌려 소수 판별을 한 뒤 개수 반환

 

결론 

완전 탐색은 자료구조 중에서 쉬운 편에 속하지만 모든 조합을 구하는 부분에서 살짝 애를 먹긴 했다. 

소수 판별해주는 에라토스테네스의 체를 확실하게 배워가는 것 같다.

컬렉션 중에서 Map과 List만 썼는데 Set도 자주 애용해야겠다.