소수 찾기

왜 재귀를 썼는가?

오늘 풀이한 순열 생성 문제와 동일한 알고리즘으로 구현했다.
https://velog.io/@magicdrill/%EB%B0%B1%EC%A4%80-16922-java-%EA%B5%AC%ED%98%84-DFS-%EC%9E%AC%EA%B7%80
재귀를 싫어하긴 하지만, 다시 연습해본다.

소수판단 함수를 왜 고쳤는가?

처음 코드는

if(num == 1 && num == 2){
     return false;
}
if(num == 2){
     return true;
}
for(i = 3; i * i <= num; i++){
   if(num % i == 0){
      return false;
   }
}

였는데, 어차피 2보다 작으면 소수가 아니고, num이 2이면

for(i = 2; i * i <= num; i++){
   if(num % i == 0){
      return false;
   }
}

반복문 내에서 i * i <= num의 조건을 만족하지 못하고 연산이 수행되지 않는다.

왜 ParseInt 순서를 바꿨는가?

처음 로직 순서는 문자열순열 구하기 -> set에 저장하기 -> 정수로 파싱하기 -> 소수여부 판단하기 였는데, 이렇게 하면 011과 11이 set에 동시에 저장이 되어 소수여부 판단에서 같은 정수인데도 두번 연산을 하게 된다. 그러므로 문자열순열 구하기 -> 정수로 파싱하기 -> set에 저장하기 -> 소수여부 판단하기로 순서를 바꿔, 중복 연산을 피한다.

import java.util.*;

class Solution {
    Set<Integer> numberSet = new HashSet<>();
    
    public int solution(String numbers) {
        int answer = 0;
        
        //numbers를 사용해 가능한 모든 순열 만들기
        generateNumbers("", numbers);

        //각각의 순열에 대해 완전탐색으로 소수 찾기
        for (int num : numberSet) {
            if (primeNumber(num)) {
                answer++;
            }
        }
        
        return answer;
    }
    
    //소수 구하기
    public boolean primeNumber(int num){
        int i;
        
        System.out.print(num);
        if(num < 2){
            System.out.println(" 소수 아님");
            return false;
        }
        for(i = 2; i * i <= num; i++){
            if(num % i == 0){
                System.out.println(" 소수 아님");
                return false;
            }
        }
        
        System.out.println(" 소수임");
        return true;
    }
    
    public void generateNumbers(String currentStr, String remainedStr){
        int i, num;
        
        if(!currentStr.equals("")){
            num = Integer.parseInt(currentStr);
            System.out.println(num);
            numberSet.add(num);
        }
        
        for (i = 0; i < remainedStr.length(); i++) {
            generateNumbers(currentStr + remainedStr.charAt(i), remainedStr.substring(0, i) + remainedStr.substring(i + 1));
        }
    }
}