[프로그래머스 Level.2] 소수 찾기 (완전탐색) (Java)

문제 링크

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

프로그래머스

 

 

 

코딩테스트 연습 > 완전탐색 > 소수 찾기

 

 

문제 설명

 

 

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

 

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

 

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 

입출력 예

numbers	return
"17"	3
"011"	2

 

입출력 예 설명

 

 

예제 #1

[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

 

 

 

예제 #2

[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

 

 

 

나의 코드

import java.util.*;

class Solution {
    boolean[] visited;
    Set<Integer> set;
    public int solution(String numbers) {
        int answer = 0;
        boolean flag = true;
        
        visited = new boolean[numbers.length()];
        set = new HashSet<>();
        
        char[] numArr = numbers.toCharArray();
        
        StringBuilder sb = new StringBuilder();
        
        dfs(numArr, sb);
        
        for(Integer s : set) {
            if(s <= 1) continue;
            
            flag = true;
            
            for(int i=2; i<=Math.sqrt(s); i++) {
                if(s%i == 0) {
                    flag = false;
                    break;
                }
            }
            
            if(flag) answer++;
        }
        
        return answer;
    }
    
    public void dfs(char[] numArr, StringBuilder sb) {
        for(int i=0; i<numArr.length; i++) {
            if(!visited[i]) {
                visited[i] = true;
                sb.append(numArr[i]);
                set.add(Integer.parseInt(String.valueOf(sb)));
                
                dfs(numArr, sb);
                visited[i] = false;
                sb.setLength(sb.length()-1);
            }
        }
    }
}

 

풀이

1. numbers를 완전탐색을 이용하여 모든 가능한 숫자를 만들어 중복을 제거하기 위해 Set에 넣고 이 숫자들 중에서 소수가 몇개인지 카운팅 해서 풀었다.
2. 우선 Integer를 선언 타입으로 하는 Set을 만들고 numbers 문자열을 완전탐색 할 때 이용하기 위해 numbers 크기의 boolean형 배열 visited를 생성한다.
3. numbers를 toCharAray()를 이용하여 char 타입 배열 numArr에 담는다.
4. 완전탐색을 하면서 모든 문자열을 만들기 위해 StringBuilder를 만들고 완전탐색 dfs(깊이 우선 탐색)을 진행한다.
5. numArr을 for문을 돌면서 인덱스를 방문하지 않았다면 StringBuilder에 append 하고 해당 StringBuilder를 Set에 담아주고 해당 인덱스를 방문했으므로 visited[i]를 true로 바꿔준다.
6. 그리고 현재 StringBuilder를 가지고 다시 dfs() 메소드를 recursive 호출하고 다음 탐색을 위해 visited[i]를 false로 바꾸고 이번에 StringBuilder에 append() 해주었던 문자를 sb.setLength(sb.length()-1)을 이용하여 제거한다.
7. 이렇게 모든 가능한 숫자들을 구해서 Set에 담아주면 중복을 제거하고 모든 숫자들이 담겨있다.
8. 이제 이 Set에 담긴 숫자들을 for each문을 돌면서 소수가 몇 개인지 카운팅하면 된다.
9. 소수(prime number)는 약수를 1과 자기 자신만 가지는 수이므로 우선 숫자 s가 1이하이면 소수가 아니니 넘어가고 2 이상이라면 flag를 두고 true로 시작해서 2 ~ 루트 s 까지 s를 나눈 나머지가 0이 되는 수가 있다면 flag를 false로 바꾼다. 2 ~ 루트 s 까지 s를 나눈 나머지가 0이 되는 수가 없다면 flag는 그대로 true 이니 answer를 증가시킨다.
10. 이렇게 하여 Set에서 소수를 카운팅하여 answer를 구해 반환한다.