[프로그래머스] 42839 소수찾기 (Lv.2) - 완전 탐색

문제

코드

재귀를 이용하여 숫자 조합을 만들고 중복을 제거하기 위해 HashSet에 저장한다. 반복문을 이용하여 HashSet에 저장된 숫자의 소수 판별을 진행하고 소수의 개수를 반환한다.

1. 재귀를 이용하여 숫자를 조합한다.
   • 중복을 피하기 위해 HashSet에 숫자를 저장한다.
2. 소수를 판별하여 소수를 카운팅한다.
   • 이때 2 ~ target -1까지 모든 숫자를 확인할 필요 없이 제곱근까지만 확인하여 시간 복잡도를 줄인다.

예전에 풀었던 문제인데도 매우 어려웠다.. 결국 전에 작성한 코드를 참고해서 풀었다...ㅠㅠ

import java.util.*;

class Solution {
    HashSet<Integer> hs = new HashSet<>();
    public int solution(String numbers) {

        // 1. 재귀로 숫자를 조합한 후 HashSet에 삽입한다.
        combination("", numbers);

        // 2. hs에 있는 값 중 소수의 개수를 구한다.(소수 판별(제곱근까지만 확인))
        int cnt = 0;
        for (int num : hs) {
            if (prime(num)) {
                cnt++;
            }
        }
        return cnt;
    }

    public void combination(String target, String arr) {
        if (!target.equals("")) 
        // Integer.valueOf()를 통해 맨 앞에 0이 온다면 무시(011, 11 -> 모두 11로 변환)
            hs.add(Integer.valueOf(target)); 

        for (int i = 0; i < arr.length(); i++) 
            combination(target + arr.charAt(i), arr.substring(0, i) + arr.substring(i + 1));
    }

    // 
    public boolean prime(int target) {
        if (target == 0 || target == 1) {
            return false;
        }
        // 2 ~ target-1까지 모두 판별할 필요 없이 제곱근까지만 확인해도 소수 판별 가능
        for(int i = 2 ; i <= Math.sqrt(target); i++){
            if(target % i == 0 ) { // 소수가 아님
                return false;
            }
        }
        return true;
    }
}

헷갈린 부분

combination()에 arr값을 인자로 넣을 때 arr에arrValue를 빼야 한다. replace() 함수를 사용하여arrValue 값을 공백으로 대체하는 방법을 사용했다. 그런데 이 경우 arrValue가 arr에서 중복되는 값일 경우 문제가 발생한다. 예를 들어 arr = "110"이고 arrValue가 '1'이라면 오류가 발생한다.

public void combination(String target, String arr) {
        if (!target.equals("")) 
        // Integer.valueOf()를 통해 맨 앞에 0이 온다면 무시(011, 11 -> 모두 11로 변환)
            hs.add(Integer.valueOf(target));

        /** 아래 코드는 중복된 숫자가 있을 경우 오류 발생
        ex. arr가 "110"이고 arrValue가 '1'일 때 앞에 1과 뒤 1중 뭘 ""로 대체할지 알 수 없음*/
        for (char arrValue : arr.toCharArray()) {
            combination(target + arrValue, arr.replace(String.valueOf(arrValue), ""));
        }
    }

위 문제를 해결하기 위해 arr.charAt(i) 값을 제외한 나머지 값만 잘라서 arr 인자로 넣는 방법을 사용했다. 처음 ~ arr.charAt(i)-1 + arr.charAt(i)+1 ~ 마지막까지의 값을 arr 인자로 넣는 방식으로 오류를 해결했다.

public void combination(String target, String arr) {
        if (!target.equals("")) 
        // Integer.valueOf()를 통해 맨 앞에 0이 온다면 무시(011, 11 -> 모두 11로 변환)
            hs.add(Integer.valueOf(target));

        /** 아래 코드는 중복된 숫자가 있을 경우 오류 발생
        ex. arr가 "110"이고 arrValue가 '1'일 때 앞에 1과 뒤 1중 뭘 ""로 대체할지 알 수 없음*/

        for (int i = 0; i < arr.length(); i++) 
            combination(target + arr.charAt(i), arr.substring(0, i) + arr.substring(i + 1));
    }

![[Pasted image 20240714031452.png]]

추가적으로 공부가 필요한 부분

• 소수 찾기
• 에라토스테네스의 체