[알고리즘] 프로그래머스 소수 찾기 (레벨 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은 같은 숫자로 취급합니다.

 

✏️ 문제 해결 방법

문제에서 숫자로 이루어진 문자열이 주어지고 이 문자열로 만들 수 있는 소수가 몇 개인지 판단하는 것이다. 여기서 '011'과 '11'은 동일한 수로 본다. 숫자가 만들어지고 나면 소수인지 판별한다. 소수는 자기자신과 1 만 약수로 가지는 숫자이다. 따라서, 소수를 구할 때는 2부터 제곱근까지만 나누어 주며 나머지가 0인 약수가 있는지 확인하면 된다. 

 

1. 숫자 저장

중복을 피해야 함으로 중복 확인이 가능한 Set 을 사용하여 Set에 만들어진 숫자들을 넣어준다. 

Set<Integer> set = new HashSet<>();

 

2. 새로운 숫자 만들기

새로운 숫자의 순서과 길이는 상관없다. 문자열에 주어진 문자를 이용해 조합을 하면 되는 것이다. 하나씩 이어 붙여주는 것이기 때문에 String 형태로 새로운 문자(숫자)를 만들어준다. 

 

재귀를 통해 주어진 숫자 문자열로 만들 수 있는 모든 조합을 만들고 이 조합을 정수로 변환하여 집합에 저장한다.

 

1) 빈 문자열이 아니라면 str을 정수로 변환하여 set에 추가한다. 

2) str에 문자열의 요소 하나 (현재 문자)를 추가하고, 이 문자를 제외한 문자들로 또 재귀 호출을 한다. 

✨ 예를들면,  numbers 가 "123"일 때 recursion("", numbers, set) 하면 이후 "1", "12", "123", "13", "132", "2", "21", "213",  ... 으로 생성되는 것이다. 

private void recursion(String str, String numbers, Set<Integer> set) {
    if (!str.isEmpty()) {
        set.add(Integer.parseInt(str));
    }

    for (int i = 0; i < numbers.length(); i++) {
        recursion(str + numbers.charAt(i), 
                             numbers.substring(0, i) + numbers.substring(i + 1), 
                             set);
    }
}

 

3. 소수 판별하기

소수는 1과 자기 자신을 약수로 가지는 1보다 큰 자연수를 말한다. num이 1보다 작거나 같으면 false를 반환하고 2부터 num의 제곱근까지 i를 증가시키며 판별해준다.

✨ num 이 소수가 아니라면 반드시 약수는 제곱근 보다 작은 수에 있기 때문에 제곱근까지만 검사해서 효율성을 높여준다.

 

1) num % i == 0 이면 약수를 가지는 것이기 때문에 false

2) 나누어지지 않으면 true를 반환한다. 

private void generatePermutations(String str, String numbers, Set<Integer> set) {
	if (!str.isEmpty()) {
		set.add(Integer.parseInt(str));
	}
        
    for (int i = 0; i < numbers.length(); i++) {
		generatePermutations(str + numbers.charAt(i), 
        numbers.substring(0, i) + numbers.substring(i + 1), set);
	}
}

 

4. set 순회하기

set 을 순회하면서 소수인지 판별을 해준다. 만약 소수가 참이라면 answer 값을 증가시켜준다. (* solution 메서드 내에 포함한다. )

int answer = 0;
for (int num : set) {
	if (num != 1 && num != 0 && isPrime(num)) {
	answer++;
	}
}

 

 

전체 코드

import java.util.*;

class Solution {
    
    public int solution(String numbers) {
        Set<Integer> set = new HashSet<>();
        recursion("", numbers, set);
        
        int answer = 0;
        for (int num : set) {
            if (num != 1 && num != 0 && isPrime(num)) {
                answer++;
            }
        }
        
        return answer;
    }

    private void recursion(String str, String numbers, Set<Integer> set) {
        if (!str.isEmpty()) {
            set.add(Integer.parseInt(str));
        }
        
        for (int i = 0; i < numbers.length(); i++) {
            recursion(str + numbers.charAt(i), 
                                 numbers.substring(0, i) + numbers.substring(i + 1), 
                                 set);
        }
    }
    
    private boolean isPrime(int num) {
        if (num <= 1) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
    
}

 

🕸️ 문제 풀이 소감

재귀로 완전탐색 시키는 것은 아직 뭔가 어렵다. 하긴 하는데 어렵다... ㅠㅠ 연습이 많이 필요할 듯 하다. 소수 판별은 이제 자주해서 보이면 isPrime 하고 있다ㅎㅎ 익숙한 부분들이 보일 때는 꽤나 뿌듯한 느낌이다. 

---

궁금한 점이 있거나 잘못된 부분이 있다면 얼마든지 댓글로 남겨주세요 🤗

감사합니다!

 

"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."