[PG] 소수 찾기 JAVA

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

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

숫자 문자열 String numbers가 주어진다.

numbers를 이루는 각 숫자들로 만들 수 있는 모든 숫자들의 조합에서 소수가 몇 개인지 반환해야한다.

단, 11과 011은 같은 것으로 치고 하나만 센다.

 

 

풀이 1. 

import java.util.*;

class Solution {
    ArrayList<Integer> pList = null;
    boolean[] check = null;
    int ans = 0;

    public boolean isPrime(int num) {
        if(num == 2 && !pList.contains(num)) {
            pList.add(num);
            return true;
        }

        if(num == 0 || num == 1 || num % 2 == 0 || pList.contains(num)) {
            return false;
        }

        for(int i = 3; i <= Math.sqrt(num); i+=2) {
            if(num % i == 0) {
                return false;
            }
        }

        pList.add(num);
        return true;
    }

    public void dfs(int dept, int deptNow, String comb, String numbers) {
        if(dept == deptNow) {  // 목표 자리수에 도달했다면 prime 검사 후 return
            int num = Integer.parseInt(comb);
            if(isPrime(num)) {
                this.ans++;
            }
            return;
        }

        // 백트래킹을 통해 모든 조합 구현
        for(int i = 0; i < numbers.length(); i++) {
            if(check[i] == false) {
                String temp = comb;  // 다시 돌아오기 위해 저장
                comb += String.valueOf(numbers.charAt(i));
                check[i] = true;

                dfs(dept, deptNow + 1, comb, numbers);

                // 백트래킹
                comb = temp;
                check[i] = false;
            }
        }
    }

    public int solution(String numbers) {
        int answer = 0;

        pList = new ArrayList<>();
        check = new boolean[numbers.length()];

        // 1~number.length() 모든 자리수의 조합을 구한다
        for(int i = 1; i <= numbers.length(); i++) {
            dfs(i, 0, "", numbers);
        }

        answer = this.ans;
        return answer;
    }
}

 

주어진 문자열로 만들어낼 수 있는 모든 조합을 구한다.

조합이 하나 완성될 때마다 소수에 해당되는지 검사한다. 

 

1. 소수 검사

기본적으로 나머지 연산을 사용한다. 이때 1 ~ num을 모두 나머지 연산 하는 것은 비효율적이다.

0, 1, 2에 대한 검사를 마친 후 3~num^(1/2) 까지만 검사하면 된다. 왜인지는 모른다.

 

2. 조합 생성

백트래킹을 사용하여 구할 수 있는 모든 조합을 구했다.

조금 걸리는 부분이 있는데.. 이렇게 짜면 number = "444333" 이렇게 같은 숫자가 반복되는 String이 주어졌을 때 똑같은 조합을 여러번 구하는 낭비가 일어난다.

444333이란 조합은 총 36개가 나오게 된다. (3! * 3!)

 

이 문제에서는 numbers의 최대길이는 7이고 7! = 5040 개의 초합이 최대이기 때문에 시간초과는 나지 않지만 n이 조금만 더 커지면 굉장히 불안해진다.. 

 

어떻게 해결할 지 생각해 봐야겠다.

 

 

 

풀이 2.

// 백트래킹을 통해 모든 조합 구현
ArrayList<Character> used = new ArrayList<>();
for(int i = 0; i < numbers.length(); i++) {
	// 다음 숫자가 이번 자리수에서 쓰인 적 있는지 검사
	if(used.contains(numbers.charAt(i))) continue;

    if(check[i] == false) {
    	String temp = comb;  // 다시 돌아오기 위해 저장
        comb += String.valueOf(numbers.charAt(i));
        used.add(numbers.charAt(i));  // 이번 자리수에서 사용된 숫자 표시
        check[i] = true;

        dfs(dept, deptNow + 1, comb, numbers);

        // 백트래킹
        comb = temp;
        check[i] = false;
	}
}

 

위 코드에서 dfs()에 코드 몇 줄을 추가하여 효율성 문제를 해결했다. (수정 전에도 시간초과 안 뜨긴 했지만)

 

각각의 dfs()는 deptNow번째 자리수에 새로운 숫자를 집어넣고 deptNow+1 번째 자리수로 재귀한다.

 

이때 각 dfs()마다 ArrayList를 두어 해당 자리수에서 한 번 사용된 숫자는 다시 사용될 수 없도록 하여 중복조합의 경우를 모두 제거했다.

 

n이 커질 경우 이를 통해 시간을 대폭 감소시킬 수 있다.

 

반복해서 생성되는 ArrayList 때문에 메모리 초과가 나지 않을까 싶긴 하지만.. 그래도 이 방법이 더 나은 듯 싶다.