- [프로그래머스 / JAVA] Level 2 메뉴 리뉴얼 (72411)
- [프로그래머스 / JAVA] Level 2 행렬 테두리 회전하기 (77485)
- [프로그래머스 / JAVA] Level 2 짝지어 제거하기 (12973)
- [프로그래머스 / MySQL] Level 2 루시와 엘라 찾기 (59046)
- [프로그래머스 / MySQL] Level 2 고양이와 개는 몇 마리 있을까 (59040)
- [프로그래머스 / JAVA] Level 2 타겟 넘버 (43165)
- [프로그래머스 / JAVA] Level 2 더 맵게 (42626)
- [프로그래머스 / JAVA] Level 2 기능개발 (42586)
- [프로그래머스 / JAVA] Level 2 124 나라의 숫자 (12899)
- [프로그래머스 / JAVA] Level 2 멀쩡한 사각형 (62048)
- [프로그래머스 / JAVA] Level 2 단체사진 찍기 (1835)
- [프로그래머스 / JAVA] Level 2 카카오프렌즈 컬러링북 (1829)
- [프로그래머스 / JAVA] Level 2 오픈채팅방 (42888)
- [프로그래머스 / JAVA] Level 2 문자열 압축 (60057)
- [프로그래머스 / JAVA] Level 1 직사각형 별찍기 (12954)
- [프로그래머스 / JAVA] Level 1 x만큼 간격이 있는 n개의 숫자 (12954)
- [프로그래머스 / JAVA] Level 1 행렬의 덧셈 (12950)
- [프로그래머스 / JAVA] Level 1 핸드폰 번호 가리기 (12948)
- [프로그래머스 / JAVA] Level 1 하샤드 수 (12947)
- [프로그래머스 / JAVA] Level 1 평균 구하기 (12944)
- [프로그래머스 / JAVA] Level 1 콜라츠 추측 (12943)
- [프로그래머스 / JAVA] Level 1 최대공약수와 최소공배수 (12940)
- [프로그래머스 / JAVA] Level 1 짝수와 홀수 (12937)
- [프로그래머스 / JAVA] Level 1 제일 작은 수 제거하기 (12935)
- [프로그래머스 / JAVA] Level 1 정수 제곱근 판별 (12934)
- [프로그래머스 / JAVA] Level 1 정수 내림차순으로 배치하기 (12933)
- [프로그래머스 / JAVA] Level 1 자연수 뒤집어 배열로 만들기 (12932)
- [프로그래머스 / JAVA] Level 1 자릿수 더하기 (12931)
- [프로그래머스 / JAVA] Level 1 이상한 문자 만들기 (12930)
- [프로그래머스 / JAVA] Level 1 약수의 합 (12928)
- [프로그래머스 / JAVA] Level 1 시저 암호 (12926)
- [프로그래머스 / JAVA] Level 1 문자열을 정수로 바꾸기 (12925)
- [프로그래머스 / JAVA] Level 1 수박수박수박수박수박수? (12922)
- [프로그래머스 / JAVA] Level 1 소수 찾기 (12921)
- [프로그래머스 / JAVA] Level 1 서울에서 김서방 찾기 (12919)
- [프로그래머스 / JAVA] Level 1 문자열 다루기 기본 (12918)
- [프로그래머스 / JAVA] Level 1 문자열 내림차순으로 배치하기 (12917)
- [프로그래머스 / JAVA] Level 1 문자열 내 p와 y의 개수 (12916)
- [프로그래머스 / JAVA] Level 1 문자열 내 마음대로 정렬하기 (12915)
- [프로그래머스 / JAVA] Level 1 두 정수 사이의 합 (12912)
- [프로그래머스 / JAVA] Level 1 나누어 떨어지는 숫자 배열 (12910)
- [프로그래머스 / JAVA] Level 1 같은 숫자는 싫어 (12906)
- [프로그래머스 / MySQL] Level 1 상위 n개 레코드 (59405)
- [프로그래머스 / JAVA] Level 1 다트 게임 (17682)
- [프로그래머스 / MySQL] Level 1 여러 기준으로 정렬하기 (59404)
- [프로그래머스 / JAVA] Level 1 가운데 글자 가져오기 (12903)
- [프로그래머스 / JAVA] Level 1 비밀지도 (17681)
- [프로그래머스 / JAVA] Level 1 부족한 금액 계산하기 (82612)
- [프로그래머스 / MySQL] Level 1 동물의 아이디와 이름 (59403)
- [프로그래머스 / JAVA] Level 1 나머지가 1이 되는 수 찾기 (87389)
- [프로그래머스 / JAVA] Level 1 최소직사각형 (86491)
- [프로그래머스 / MySQL] Level 1 어린 동물 찾기 (59037)
- [프로그래머스 / JAVA] Level 1 2016년 (12901)
- [프로그래머스 / MySQL] Level 1 아픈 동물 찾기 (59036)
- [프로그래머스 / JAVA] Level 1 두 개 뽑아서 더하기 (68644)
- [프로그래머스 / MySQL] Level 1 이름이 있는 동물의 아이디 (59407)
- [프로그래머스 / JAVA] Level 1 두 개 뽑아서 더하기 (12982)
- [프로그래머스 / JAVA] Level 1 예산 (12982)
- [프로그래머스 / JAVA] Level 1 3진법 뒤집기 (68935)
- [프로그래머스 / JAVA] Level 1 약수의 개수와 덧셈 (77884)
- [프로그래머스 / JAVA] Level 1 실패율 (42889)
- [프로그래머스 / JAVA] Level 1 폰켓몬 (1845)
- [프로그래머스 / MySQL] Level 1 이름이 없는 동물의 아이디 (59039)
- [프로그래머스 / MySQL] Level 1 최댓값 구하기 (59415)
- [프로그래머스 / MySQL] Level 1 모든 레코드 조회하기 (59034)
- [프로그래머스 / JAVA] Level 1 체육복 (42862)
- [프로그래머스 / JAVA] Level 1 모의고사 (42840)
- [프로그래머스 / JAVA] Level 1 완주하지 못한 선수 (42576)
👀 [프로그래머스 / JAVA] Level 1 소수 만들기 (12977)
- [프로그래머스 / JAVA] Level 1 음양 더하기 (76501)
- [프로그래머스 / JAVA] Level 1 K번째수 (42748)
- [프로그래머스 / JAVA] Level 1 내적 (70128)
- [프로그래머스 / JAVA] Level 1 없는 숫자 더하기 (86051)
- [프로그래머스 / JAVA] Level 1 크레인 인형뽑기 게임 (64061)
- [프로그래머스 / JAVA] Level 1 키패드 누르기 (67256)
- [프로그래머스 / JAVA] Level 1 숫자 문자열과 영단어 (81301)
- [프로그래머스 / JAVA] Level 1 신규 아이디 추천 (72410)
- [프로그래머스 / JAVA] Level 1 로또의 최고 순위와 최저 순위 (77484)
소수 만들기 🔗
🔗 소수 만들기
문제 설명 🔗
주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums
가 매개변수로 주어질 때, nums
에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution
함수를 완성해주세요.
제한사항 🔗
nums
에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.nums
의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.
입출력 예 🔗
nums | result |
---|---|
{ 1, 2, 3, 4 } | 1 |
{ 1, 2, 7, 6, 4 } | 4 |
입출력 예 설명 🔗
입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.
입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.
풀이 🔗
배열에서 임의의 요소 3가지를 선택하여 해당 수의 합이 소수가 되는 경우의 수를 구하는 문제.
- 임의의 요소 3가지 선택
- 요소의 합의 소수 여부 판별
이 두 로직을 구현하는 것이 알고리즘의 핵심이다.
보통 조합을 이용하지만, 간단하게 중첩 for
문을 사용해 구현해보자.
JAVA
0 | for (int i = 0; i < nums.length; i++) |
1 | { |
2 | for (int j = i + 1; j < nums.length; j++) |
3 | { |
4 | for (int k = j + 1; k < nums.length; k++) |
5 | { |
6 | int sum = nums[i] + nums[j] + nums[k]; |
7 | } |
8 | } |
9 | } |
임의의 세 가지 요소는 이와 같이 3중첩 for
문을 통해 구할 수 있다. j
, k
의 인덱스를 유심히 살펴보자. 각 인덱스가 겹치지 않게끔 초기값이 구성되어있다.
JAVA
0 | private boolean isPrime(int num) |
1 | { |
2 | for (int i = 2; i <= Math.sqrt(num); i++) |
3 | { |
4 | // 나눠 떨어질 경우 |
5 | if (num % i == 0) |
6 | { |
7 | return false; |
8 | } |
9 | } |
10 | |
11 | return true; |
12 | } |
소수는 이와 같이 구할 수 있다. 굳이 Math.sqrt(num)
까지만 연산히는 이유는, 제곱근 이후로는 연산할 필요가 없다.
예를 들어, 12의 경우 1, 2, 3, 4, 6, 12
의 약수를 가지는데, 는 대략 3이다. 3 이후의 숫자인 4, 6은 각각 2와 3과 곱해져서 12를 만들게 되므로, 제곱근 이전에 나누어 떨어지는 수가 없다면 그 수는 소수라 봐도 무방하다.
코드 🔗
JAVA
0 | /** |
1 | * 소수 만들기 클래스 |
2 | * |
3 | * @author RWB |
4 | * @since 2021.12.10 Fri 00:21:09 |
5 | */ |
6 | class Solution |
7 | { |
8 | /** |
9 | * 해답 반환 메서드 |
10 | * |
11 | * @param nums: [int[]] 숫자 배열 |
12 | * |
13 | * @return [int] 소수가 되는 경우의 수 |
14 | */ |
15 | public int solution(int[] nums) |
16 | { |
17 | int answer = 0; |
18 | |
19 | for (int i = 0; i < nums.length; i++) |
20 | { |
21 | for (int j = i + 1; j < nums.length; j++) |
22 | { |
23 | for (int k = j + 1; k < nums.length; k++) |
24 | { |
25 | int sum = nums[i] + nums[j] + nums[k]; |
26 | |
27 | answer += isPrime(sum) ? 1 : 0; |
28 | } |
29 | } |
30 | } |
31 | |
32 | return answer; |
33 | } |
34 | |
35 | /** |
36 | * 소수 여부 반환 메서드 |
37 | * |
38 | * @param num: [int] 숫자 |
39 | * |
40 | * @return [boolean] 소수 여부 |
41 | */ |
42 | private boolean isPrime(int num) |
43 | { |
44 | for (int i = 2; i <= Math.sqrt(num); i++) |
45 | { |
46 | // 나눠 떨어질 경우 |
47 | if (num % i == 0) |
48 | { |
49 | return false; |
50 | } |
51 | } |
52 | |
53 | return true; |
54 | } |
55 | } |
📆 작성일
2021-12-14 Tue 10:06:57
📚 카테고리
🏷️ 태그