[프로그래머스/java] 소수찾기 - 백트래킹 사용(예제 코드 포함)

 

https://programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

 

소수찾기 - 백트래킹

 

문제의 카테고리가 완전탐색이다.

 

완전탐색은? 바로 백트래킹을 쓰면 된다.

 

모든 조합을 브루트 포스로 다 구하면 모든 경우에 대해서 값을 다 구할 수 있다.

 

다음은 백트래킹 예시이다.

 

int val = 0;
boolean[] check = new boolean[len];

public void backTracking(int len, int limit, String[] arr) {
	if(len == limit) {
    	val++;
    	return;
    }
    
    for(int i = 0; i < arr.length; i++) {
    	if(!check[i]) {
        	check[i] = true;
            backTracking(len + 1, limit, arr);
            check[i] = false;
        }
    }
}

 

주어진 조건(길이나 갯수)에 충족했을 때, 구해야하는 갯수를 증가시키면 되고,

 

중복이 허용되지 않는 경우는 위처럼 확인했는지 안했는지(= if(!check[i]) )를 확인해주어야 한다.

 

확인되지 않은 인덱스면 계속 재귀적으로 탐색할 때 해당 인덱스를 다시 방문하지 못하도록 check[i]를 true로 주어야 다시 방문하지 않는다.

 

true로 방문 여부를 체크해주고 재귀적으로 len을 1 증가하여 탐색 메서드인 backTracking()을 또 호출하는 방식으로 백트래킹을 사용하면 된다.

 

그리고, 소수를 구해야하기 때문에 아래와 같은 로직으로 소수를 구한다.

 

    public boolean isPrimeNumber(String str) {
    	int num = Integer.parseInt(str);
    	
    	for (int i = 2; i <= Math.sqrt(num); i++) {
			if(num % i == 0) return false;
		}
    	
    	return true;
    }

 

num이 소수(1과 자기 자신으로 나누어지는 수)가 아니면 false, 맞으면 true를 리턴한다.

 

※ 소수 찾는 로직 참고 블로그 : https://freedeveloper.tistory.com/391

 

Math.sqrt(number) 를 사용하면 처음부터 조사해야할 수의 경우가 확 줄어든다.

 

따라서 Math.sqrt(num)까지 for문을 순회하면

과 같은 시간복잡도가 나오게 된다.

 

package findPrimeNumber;

import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

public class FindPrimeNumber {
	public static void main(String[] args) {
		Solution s = new Solution();
		System.out.println(s.solution("17"));
		System.out.println(s.solution("011"));
	}
}

class Solution {
	boolean[] check;
	Map<Integer, Boolean> map;
	int len;
	
    public int solution(String numbers) {
    	len = numbers.length();
        check = new boolean[len];
        map = new HashMap<Integer, Boolean>();
        
        String[] card = numbers.split("");
        
        Arrays.sort(card, Collections.reverseOrder());
        search(card, "");
        
        return map.size();
    }
    
    public void search(String[] card, String str) {
    	if(len == str.length()) return;
    	
    	for (int i = 0; i < card.length; i++) {
			if(!check[i]) {
				check[i] = true;
				String temp = str + card[i];
				int num = Integer.parseInt(str + card[i]);
				boolean isPrime = false;
				if(num >= 2) isPrime = isPrimeNumber(temp);
				if(isPrime && !map.containsKey(num)) map.put(num, true);
				search(card, temp);
				check[i] = false;
			}
		}
    }
    
    public boolean isPrimeNumber(String str) {
    	int num = Integer.parseInt(str);
    	
    	for (int i = 2; i <= Math.sqrt(num); i++) {
			if(num % i == 0) return false;
		}
    	
    	return true;
    }
}