[프로그래머스] 12977 소수 만들기
프로그래머스 level2
문제
문제 풀이
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| static int count = 0; | |
| public int solution(int[] nums) { | |
| boolean[] visited = new boolean[nums.length]; | |
| combination(nums, visited, 0, nums.length, 3); | |
| return count; | |
| } | |
| // 조합 : 중복X, 순서X - 백트래킹 | |
| // nums - 조합을 뽑아 배열, visited - 조합에 뽑혔는지 체크하는 배열, n - 배열의 길이, r - 조합의 길 | |
| // start를 기준으로 start 보다 작으면 뽑을 후보에서 제외, start 보다 크면 뽑을 후보가 된다. | |
| public void combination(int[] nums, boolean[] visited, int start, int n, int r) { | |
| if (r == 0) { | |
| int sum = 0; | |
| for (int i = 0; i < n; i++) { // 3개의 수 합 구하기 | |
| if (visited[i]) { | |
| sum += nums[i]; | |
| } | |
| } | |
| if (isPrime(sum)) { //합이 소수인지 확인하기 | |
| count++; //소수이면 값 증가 | |
| } | |
| return; | |
| } else { | |
| for (int i = start; i < n; i++) { | |
| visited[i] = true; | |
| combination(nums, visited, i + 1, n, r - 1); | |
| visited[i] = false; | |
| } | |
| } | |
| } | |
| // 소수 판별 함수 | |
| public boolean isPrime(int n){ | |
| if (n <= 1) { | |
| return false; | |
| } | |
| int a = (int) Math.sqrt(n); | |
| for (int j = 2; j <= a; j++) { | |
| if (n % j == 0) { | |
| return false; | |
| } | |
| } | |
| return true; | |
| } | |
| } |
문제 리뷰
주어진 배열에서 3개의 수를 더한 값이 소수가 되는 경우를 찾는 문제이다.
- 나는 조합을 이용하여 문제를 풀이했다.
- 저번에 비숫한 문제 를 순열로 풀었던터라 쉽게 방법을 떠올릴 수 있었다.
- 조합을 사용하면 중복과 순서 없이 수를 뽑을 수 있다.
- 조합 코드는 아래의 블로그 포스팅을 참고했다. 설명을 아주 쉽게 해놓으셨다!
조합으로 3개의 수를 뽑고 그 수의 합이 소수인지 판별한 후, 카운팅 해주었다.
사실 풀면서 완전탐색, 전역변수를 사용한터라
시간초과가 나지 않을까 걱정했는데 다행히 모두 통과했다.
좀 더 효율성 높은 방법을 고민해봐야겠다.
참고
TMI
불금!
1일 1알고리즘 완료🤓
댓글남기기