prgms.12977 - 소수의 개수
문제 분석
- 문제 유형 : 브루트 포스
- 걸린 시간 : 24분 32초
- 풀이 전략 : nums에 있는 여러 개의 수 중에서 서로 다른 3개만 골라서 -> 합을 구한 뒤 -> 소수인지 판별하고, 소수이면 answer++
- 걸렸던 부분 : 여러 개의 수 중에서 3개가 중복되지 않게 골라야하는데 단순히 반복문을 돌아서는 구할 수 없다. 그래서 반복문으로 바로 떠오르지 않아 nC3조합을 구하는 방법으로 구현하였다.
나의 풀이
combination 메서드를 구현하여 nC3을 돌리고 그 안에서 isPrime 메서드를 호출하여 소수여부를 판단한다. 소수이면 answer++를 수행한다.
combination을 직접 구현하는게 아직 익숙하지 않아서 웹 상에서 참조하여 수정했다. 자바에서는 반드시 암기해야할 부분이다.
- 참조 링크 : https://bcp0109.tistory.com/15
class Solution {
int answer = 0;
public int solution(int[] nums) {
int n = nums.length;
boolean[] visited = new boolean[n];
combination(nums, visited, 0, n, 3);
return answer;
}
private void combination(int[] arr, boolean[] visited, int depth, int n, int r) {
if (r == 0) {
int sum = sum(arr, visited, n);
if (isPrime(sum)) answer++;
return;
}
if (depth == n) {
return;
}
visited[depth] = true;
combination(arr, visited, depth + 1, n, r - 1);
visited[depth] = false;
combination(arr, visited, depth + 1, n, r);
}
private int sum(int[] arr, boolean[] visited, int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
if (visited[i]) {
sum += arr[i];
}
}
return sum;
}
private boolean isPrime(int num) {
for (int i = 2; i < num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
}
다른 사람의 풀이
내가 막혔던 부분인 3중 for문에서 인덱스를 0부터 시작하는게 아니라 각 바깥 반복문 인덱스 + 1로 시작하여 끝 부분에서는 겹치지않게 그만큼 빼준다.
i : 0 1 2 3 4 5 6 7 8
j : 1 2 3 4 5 6 7 8 9
k : 2 3 4 5 6 7 8 9 10
3개라는 제한이 있기 때문에 3중 for문으로 충분히 해결 가능하지만 무수히 많은 수를 검사해야하거나 변수로 주어진다면 조합이나 재귀를 이용한 방법으로 해결하는 것이 바람직할 것이다.
import java.util.Arrays;
class Solution {
public int solution(int[] nums) {
int ans = 0;
for(int i = 0; i < nums.length - 2; i ++){
for(int j = i + 1; j < nums.length - 1; j ++){
for(int k = j + 1; k < nums.length; k ++ ){
if(isPrime(nums[i] + nums[j] + nums[k])){
ans += 1;
}
}
}
}
return ans;
}
public Boolean isPrime(int num){
int cnt = 0;
for(int i = 1; i <= (int)Math.sqrt(num); i ++){
if(num % i == 0) cnt += 1;
}
return cnt == 1;
}
}