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

 

 

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

문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

---

풀이

소수는 1과 자기 자신을 제외한 나머지 자연수로 나눠지지 않는 수를 의미한다. isPrime()라는 함수를 만들어 해당 함수의 파라미터로 들어오는 수(number)를 for문을 통해 2부터 number-1까지 나누어서 한번이라도 나누어떨어진다면 false를 리턴하고, 그렇지 않은 경우에는 true를 리턴하도록 했다. (0 과 1은 소수가 아니기때문에 false를 리턴)

 

소수 판별의 대상이 되는 수는 입력값 numbers를 쪼개서 조합되는 수이다. search() 함수에서 만들 수 있는 조합을 만드는 로직을 수행하도록 하였다.

 

만들어진 소수는 중복의 경우 세지 않는다. 그렇기 때문에 HashSet 자료구조를 사용하여 중복을 제거하도록 하였고, 결과는 set의 size를 리턴하였다.

 

코드

import java.util.HashSet;
import java.util.Set;

public class Solution {

    private String[] pieces;
    private boolean[] visited;
    private Set<Integer> answer;

    public int solution(String numbers) {
        answer = new HashSet<>();
        pieces = new String[numbers.length()];
        visited = new boolean[numbers.length()];

        for (int i = 0; i < numbers.length(); i++) {
            pieces[i] = String.valueOf(numbers.charAt(i));
        }

        for (int i = 0; i < pieces.length; i++) {
            visited[i] = true;
            search(String.valueOf(pieces[i]), 0);
            visited[i] = false;
        }

        return answer.size();
    }

    private void search(String number, int count) {
        if (isPrime(Integer.parseInt(number))) {
            answer.add(Integer.parseInt(number));
        }

        for (int i = 0; i < pieces.length; i++) {
            if (visited[i]) {
                continue;
            }

            visited[i] = true;
            dfs(number + pieces[i], count + 1);
            visited[i] = false;
        }
    }

    private boolean isPrime(int number) {
        if(number < 2) {
            return false;
        }

        for(int i = 2; i < number; i++) {
            if(number % i == 0) {
                return false;
            }
        }
        
        return true;
    }
}