99클럽 코테 스터디 10일차 TIL - DFS, 재귀

오늘의 학습 키워드

재귀

---

알고리즘 문제

• 프로그래머스 Level 2. 소수찾기
• https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

---

공부한 내용

재귀

• 자기 자신을 호출한다.
• 재귀함수를 호출할 때마다 Stack 메모리에 할당된다. (재귀함수 내 종료 조건이 필요한 이유)
• 만약 재귀함수 내 종료 조건이 없고 무한 반복되면? => stack overflow 발생
• return; 또는 "}"를 만나 함수가 리턴되면 호출된 곳으로 돌아간다는 의미!

---

오늘의 회고

처음 시도

• 예시로 준 "17"과 세자리 수 "123"의 조합 경우의 수를 끄적여보았다.
• 어떻게 탐색해야 할지 고민했다.
• 단순 반복문을 돌리려다 너무 복잡해져서 재귀를 알아보았다.

해결

• 재귀를 활용해 주어진 numbers에서 숫자를 하나 Pick 해두고 그 외의 숫자를 오른쪽에 붙여가며 조합하여 모든 숫자를 조합해서 탐색하는 방법으로 해결했다.

---

문제 풀이

import java.util.*;

class Solution {
	Set<Integer> numSet = new HashSet<>();	// 조합 완성된 숫자
	Set<Integer> result = new HashSet<>();	// 소수까지 판별된 숫자
    
    //현재 조합된 숫자(comb), 남은 숫자(remains)로 모든 숫자 조합
    public void reculsive(String comb, String remains) {
    	//첫 번째 호출은 ""이므로 예외
        if(!comb.equals(""))
            numSet.add(Integer.parseInt(comb));
        
        //재귀 종료: remains 길이만큼 반복 호출 => remains 전체 숫자를 반복해서 조합하면 종료
        for (int i = 0; i < remains.length(); i++) {
            //1.처음 remains의 i번째 인덱스를 pick하고, pick한 숫자를 제외한 나머지 숫자를 remains로
            //2.pick한 숫자를 comb 오른쪽에 붙임.
            //3.remains의 길이가 0이 될때까지 조합
            reculsive(comb + remains.charAt(i), remains.substring(0,i) + remains.substring(i+1));
        }
    }
    
    //소수 체크
    public boolean check(int num) {
        if (num < 2) return false;
        for (int i = 2; i*i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
    
    public int solution(String numbers) {
        
        reculsive("", numbers);
        
        for(int i : numSet) {
            if(check(i))
                result.add(i);
        }
        
        return result.size();
    }
}

 

다른 사람의 풀이

• HashSet.iterator()를 사용
• 제곱근을 Math.sqrt()를 사용해 표현

import java.util.HashSet;
class Solution {
    public int solution(String numbers) {
        HashSet<Integer> set = new HashSet<>();
        permutation("", numbers, set);
        int count = 0;
        while(set.iterator().hasNext()){
            int a = set.iterator().next();
            set.remove(a);
            if(a==2) count++;
            if(a%2!=0 && isPrime(a)){
                count++;
            }
        }        
        return count;
    }

    public boolean isPrime(int n){
        if(n==0 || n==1) return false;
        for(int i=3; i<=(int)Math.sqrt(n); i+=2){
            if(n%i==0) return false;
        }
        return true;
    }

    public void permutation(String prefix, String str, HashSet<Integer> set) {
        int n = str.length();
        if(!prefix.equals("")) set.add(Integer.valueOf(prefix));
        for (int i = 0; i < n; i++)
          permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);

    }

}