[Java | Algorithm] 프로그래머스 Lv2 - 소수 찾기

출처 - https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

1) 문제 설명

2) 접근 방식

문제 자체는 이해하기 어렵지 않았습니다.

소수 판단하는 함수와 dfs방식으로 백트래킹을 사용하는 함수를 사용하면 되겠다라는 게 제 접근 방식이였습니다.

// 소수 판단하기
static boolean isPrime(int n) {
	if(n<2) return false;
		
	for(int i=2; i*i<=n; i++) {
		if(n % i == 0) return false;
	}
		
	return true;
}

위 코드로 소수 판단하는 함수는 쉽게 구현했습니다.

문제는 dfs를 어떻게 구현할까 였습니다.

전체 경우의 수를 찾아야하니까 백트래킹을 써야한다는 것은 알겠는데 아직도 구현은 잘 못하는 것 같습니다.
그렇게 처음엔 풀지 못하고

[Java | Algorithm] BackTracking (백트래킹) 이해하기

예전에 작성했던 글을 보면서 백트래킹을 다시 공부하고 다른 글도 참고하면서 다시 풀어봤습니다.

3) 풀이

import java.io.*;
import java.util.*;
class Solution {
    static HashSet<Integer> set = new HashSet<>(); // 중복값 제거 위한 set
    static char[] arr; // 종이 조각
    static boolean[] visited; // 사용여부
    
    public int solution(String numbers) {
        int answer = 0;
        arr = new char[numbers.length()];
        visited = new boolean[numbers.length()];
        
        for(int i=0; i<numbers.length(); i++){
            arr[i] = numbers.charAt(i); // 종이 조각 담기
        }
                
        dfs("",0); 
        
        answer = set.size();
        return answer;
    }
	//백트래킹
	static void dfs(String str, int idx) {
        int num;
            
        if(str!=""){
            num = Integer.parseInt(str);
            if(isPrime(num)) set.add(num); // 소수판별
        }
        if(idx==arr.length) return; // 끝까지 다했을 때 
        
        for(int i=0;i<arr.length;i++){
            if(visited[i]) continue; // 방문한 노드면 넘어감
            visited[i] = true; // 방문

            dfs(str+arr[i], idx+1); // 방문 했을 시 재귀

            visited[i] = false; // 백트래킹
        }
		
	}
    
	//소수 판단
	static boolean isPrime(int n) {
		if(n<2) return false;
		
		for(int i=2; i*i<=n; i++) {
			if(n % i == 0) return false;
		}
		
		return true;
	}

}

일단 전체 코드입니다.

처음부터 보면

dfs를 돌면서 숫자를 저장하는 중복된 소수는 저장이 되지 않도록 HashSet으로 set을 선언해주고

종이 조각을 하나씩 담을 arr배열과 사용여부를 체크할 visited 배열을 선언해줍니다.

이제 젤 중요한 백트래킹 코드를 보면

//백트래킹
static void dfs(String str, int idx) {
    int num;

    if(str!=""){
        num = Integer.parseInt(str);
        if(isPrime(num)) set.add(num); // 소수판별
    }
    if(idx==arr.length) return; // 끝까지 다했을 때 

    for(int i=0;i<arr.length;i++){
        if(visited[i]) continue; // 방문했으면 넘어감
        visited[i] = true; // 방문

        dfs(str+arr[i], idx+1); //재귀

        visited[i] = false; // 백트래킹
    }

}

visited 배열을 통해 방문했으면 넘어가고
방문하지 않았을 때 방문체크(true)를 해주고 다시 재귀함수로 들어갑니다.

모든 경우의 수를 탐색해야하기 때문에 visited는 다시 false로 돌려줍니다.

 

str이 빈 문자열이 아닐때 문자 str을 숫자로 변환 후 소수 체크를 하여 isPrime(num) 이 true이면 set에 넣어줍니다.

 

다 돌고나와서

set.size() 로 set 크기를 구하면 답이 나옵니다.

 

추가적으로 소수 판단은 에라토스테네스의 체를 활용하여

숫자 n이 주어졌을 때 n의 제곱근 이하 자연수로 나누어 떨어지는 지 확인하는 방법이 있었습니다.

public static boolean isPrime(int n) {
    if (n < 2) {
        return false;
    }
    // 에라토스테네스 체
    for (int i = 2; i <= (int) Math.sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

정리

정리하면서 풀어보니 엄청 어려운 문제도 아니였는데 많이 헤맸던 것 같습니다.
다시 동기 부여를 받고 열심히 많은 문제를 풀면서 실력을 향상시켜야겠습니다.
완전탐색은 모든 경우의 수를 찾는 문제이고 천천히 생각하면서 풀자!!