일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- Java
- 프로그래머스
- 자바
- 명령어
- Linux
- 스프링 빈
- java 백준 1차원 배열
- Kotlin
- 고잉버스
- 개발자 회고록
- 코테
- JavaScript
- 코딩테스트
- 카카오
- toCharArray
- 리눅스마스터 3과목
- 리눅스마스터1급
- 리눅스
- 스프링 컨테이너
- 문자열
- Memoir
- 백준 java
- 월간코드챌린지
- GoingBus
- map
- 반복문
- 리눅스마스터 1급 정리
- 자바스크립트 코딩의 기술
- 백준 javascript
- 연습문제
- Today
- Total
hoon's bLog
[Java] 프로그래머스 소수 만들기 자바 본문
문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/12977
[나의 풀이]
- 반복문 중첩을 통해 3개의 수를 선택하여 합
- chkSum 함수로 자기 자신보다 작은 수로 나누어 떨어지지 않을 경우 소수로 판별하여 true return!
- chkSum 함수가 true retrun 일 때만 +
class Solution {
public int solution(int[] nums) {
int answer = 0;
int tmp1, tmp2, tmp3;
int sum = 0;
for(int i=0; i<nums.length-2; i++){ //첫번째 수 선택
tmp1 = nums[i];
for(int j=i+1; j<nums.length; j++){ //두번째 수 선택
tmp2 = nums[j];
for(int k=j+1; k<nums.length; k++){ //세번째 수 선택
tmp3 = nums[k];
sum = tmp1 + tmp2 + tmp3;
if(chkSum(sum) == true)
answer++;
}
}
}
return answer;
}
//3개의 수 합보다 작은 수로 나눴을 때 0으로 떨어지지 않을때 true return
private boolean chkSum(int sum) {
for(int l=2; l<sum; l++){
if(sum%l == 0) return false;
}
return true;
}
}
재귀 함수까지는 아니지만,
반복해서 사용하는 부분에 대해서 함수로 분리해 봤다.(현실은 섬멀티 for문...ㅎㅎㅎ)
반복문이 낭자하는 이 코드...
다른 분들은 또 어떻게 했을까?!?!?
[다른 사람의 풀이]
public class Solution{
public static int result = 0;
public int solution(int[] nums) {
int answer = 0;
int n = nums.length; //n=4
int r = 3;
int[] arr = new int[n];
//combination(배열변수, 인덱스, 입력배열길이, 고르는 숫자개수, 입력배열용 인덱스, 입력배열)
combination(arr, 0, n, r, 0, nums);
answer = result;
return answer;
}
public static void combination(int[] arr, int index, int n, int r, int target, int[] nums) {
if (r == 0) //입력 배열 nums에서 숫자 3개를 고름
print(arr, index);
else if (target == n)
return;
else {
arr[index] = nums[target];
combination(arr, index + 1, n, r-1, target + 1, nums);
combination(arr, index, n, r, target + 1, nums);
}
}
public static void print(int[] arr, int length) {
int cnt = 0;
boolean isPrime = false;
for (int i = 0; i < length; i++) {
cnt += arr[i];
}
// 1과 num 자신 외에 나누어지는 수가 있는지 검사할 조건문
for (int i = 2; i < cnt; i++) {
if (cnt % i == 0) {
// 나누어 떨어지는 경우 isPrime의 값 = true
// 한 번이라도 이 조건문이 실행될 경우 num은 소수가 아니므로 반복문을 빠져나온다.
isPrime = true;
break;
}
}
if (!isPrime) result++;
}
}
이번 다른 사람의 코드는 조합(Combination)의 개념을 이용한 재귀 함수 방식이다!
중/고등학교 때 배운 수학 개념이기에 오랜만에 구글링을 하며 다시 되짚어 본다....
조합(Combination) : n개의 원소에서 r개의 원소를 순서 상관없이 뽑는 경우의 수
[공식]
nCr = nPr / r!
= n! / (n-r)! * r!
= n-1Cr-1 + n-1Cr
진하게 표시되었듯, 여기서 핵심은 마지막 줄의 공식이다!
[정리]
- 알고리즘 문제에서 소수의 개념은 자주 나오니 반복문을 이용하여 자기 자신만 나눠 떨어지는 수 기억할 것!
- 반복문과 조건문이 복잡해지거나, 빈번하게 사용되는 부분은 함수로 꼭 분리해주는 습관을 들이자!
- 반복문을 반복해서 사용하기보다, 재귀 함수를 이용하여 사고하는 방식도 꾸준히 연습할 것!
개인피셜 난이도 : ★★☆☆☆
반복문이 중첩이 되는 것을 보고 재귀 함수를 써야 한다는 건 알았지만,
다른 분이 코딩한 소스처럼 해야겠다는 알고리즘 사고가 떠오르지 않았다...
심지어 지금도 동작 로직이 잘 이해가 되지 않는 상태!.....
(혹시나 지나가다가 말로 잘 표현해주실 분 댓글로 남겨주시면 정말 감사하겠습니다!ㅜㅜ)
이해가 되는대로 조만간 수정하여 업로드하도록 하겠다!....
끝!
* 참고 블로그
- 조합(Combination) 개념 : https://woongsios.tistory.com/179
- 조합 로직 예제 : https://minhamina.tistory.com/38
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
[Java] 프로그래머스 폰켓몬 자바 (0) | 2022.06.16 |
---|---|
Java 프로그래머스 예산 자바 (0) | 2022.06.15 |
[Java] 프로그래머스 부족한 금액 계산하기 자바 (0) | 2022.06.14 |
Java 프로그래머스 최소 직사각형 자바 (0) | 2022.06.14 |
Java 프로그래머스 나머지가 1이 되는 수 찾기 자바 (0) | 2022.06.13 |