소수 찾기

링크텍스트

문제 설명

1. numbers를 완전탐색하여 조합할 수 있는 수를 만든다.
2. 소수인지 판별

시행착오 및 풀이 방법

사실 문제를 풀기 전에 완전탐색 카테고리인 걸 봐버려서 재귀는 쉽게 떠올렸다.
근데 뭐,,,, 숫자 하나하나 조합해서 만드는거니깐 무난하게 재귀는 떠올렸을듯?! (자의식과잉)

정답 풀이

1. 중복을 제거해야 하므로 set 사용
2. 재귀함수로 수 만들기
   2-1. 쉽게 생각해보자면 "numbers를 하나하나 찢어서 맨 앞에 숫자 하나(s) 두고 나머지 숫자(others)에서 하나 빼서 붙이고 또 하나 빼서 붙이는 과정을 반복해서 만든 수를 set에 넣기" 라고 생각하면서 풀었음 (재귀는 복잡하고 어려워서 곰곰히 생각하면서 풀어야 했음ㅠㅠ)
   결론은 완탐!!
3. 소수 판별
   3-1. 0이나 1이면 소수가 아님
   3-2. 효율성을 위해 Math.sqrt한 부분까지 for문 돌리면서 약수가 발견되면 바로 false(소수가 아님) 반환
   3-3. for문 도는 동안 끝까지 약수가 없으면 소수인 것이므로 true 반환
4. 소수라면 answer++ -> 반환

정답 코드

import java.util.*;
class Solution {
    static HashSet<Integer> set = new HashSet<>();
    public int solution(String numbers) {
        int answer = 0;
        
        //수 만들기
        recursive("", numbers);
        
        //소수 판별
        for(int n:set) {
            //소수라면
            if(prime(n)) {
                answer++;
            }
        }
        
        return answer;
    }
    
    //수 만들기
    public void recursive(String s, String others) {
        //비어있지 않은 문자열이라면 set에 넣기
        if(!s.equals("")) {
            set.add(Integer.valueOf(s));
        }
        
        //재귀
        for(int i=0; i<others.length(); i++) {
            recursive(s+others.charAt(i), others.substring(0,i)+others.substring(i+1));
        }
    }
    
    public boolean prime(int n) {
        if(n == 0 || n == 1) {
            return false;
        }

        for(int j = 2; j <= Math.sqrt(n); j++) {
            if(n % j == 0) {
                return false;  //약수가 발견되면 바로 false 반환
            }
        }

        return true;  //끝까지 약수가 없으면 true 반환
    }
}

시행착오

오늘의 시행착오는 뭐.. 소수 판별할 때 0이나 1이면 false를 반환해야지! 라고 생각해놓고 손으로는 1이나 2면 false~ 하는 바람에 답이 잘못 나온 정도..? 와중에 어디가 틀렸는지 못찾아서 확인하는 코드 추가한 정도....?

//확인용
        // System.out.println("numbers: " + set);
        // for(int n:set) {
        //     System.out.println("Checking: " + n + " -> " + prime(n));
        // }

디버깅하니깐 원인을 바로 알아낼 수 있었음 굿~

소수 문제는 효율성을 위해 Math.sqrt() 사용하는 것 잊지 말기!

---

완전탐색, 재귀 너무 어렵다... 원리는 이해했는데 뭔가 머릿속으로 잘 안그려지는 느낌.....
그리고 옛날에는 함수를 분리해서 만드는 것이 어렵다고 생각했는데 이젠 분리 안하면 불편함
약간 스프링부트 플젝에서 코딩할 때 모듈화를 엄청 신경 썼던 것 같은데 거기서 파생된 습관일라나..?
긍정적 효과 나이스~