문제 설명
주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어졌을 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.
제한사항
- nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
- nums의 원소는 1이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.
입출력 예
nums | result | 설명 | ||
[1, 2, 3, 4] | 1 | [1, 2, 4]를 이용해서 7을 만들 수 있습니다. | ||
[1, 2, 7, 6, 4] | 4 | [1, 2, 4]를 이용해서 7을 만들 수 있습니다. [1, 4, 6]을이용해서 11을 만들 수 있습니다. [2, 4, 7]을 이용해서 13을 만들 수 있습니다. [4, 6, 7]을 이용해서 17을 만들 수 있습니다. |
문제 풀이
풀이 언어 : C++
#include <vector>
using namespace std;
bool is_prime_num(int num)
{
// 2인 경우 소수
if(num==2)
{
return true;
}
// 2가 아닌 경우 소수 검사
for(int i=2; i<num; i++)
{
// 1과 자기 자신만이 아닌 다른 수로 나누어 진다면
if(num%i==0)
{
return false; // 소수
}
}
return true;
}
int solution(vector<int> nums) {
int answer = 0;
// 3개의 수 더하기
for(int i=0; i<nums.size()-2; i++)
{
for(int j=i+1; j<nums.size()-1; j++)
{
for(int k=j+1; k<nums.size(); k++)
{
// 3개의 수를 더한게 소수라면
if(is_prime_num(nums[i]+nums[j]+nums[k]))
{
answer++; // answer 업데이트
}
}
}
}
return answer;
}
두 개의 기능만 구현하면 풀 수 있는 문제다. 첫째는 벡터 중 중복 없이 3개의 수를 골라내는 기능이고, 둘째는 특정 수가 소수인지 구별해는 것이다.
우선 여러 수가 들어있는 벡터에서 세 개의 수를 골라내고 그 수의 합을 구하는 방법이다. 분명 이런 기능을 구현해보았던 기억이 있어서 이전에 풀었던 문제를 찾아보았다.
https://iiblueblue.tistory.com/156
[2025.01.16] 삼총사
문제 설명한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어 5명의 학생이 있고,
iiblueblue.tistory.com
for문 세 개를 이용한 방법이다. 가장 큰 반복문은 i=0~nums.size()-2 반복문을 돌리고 중간 반복문은j=i+1~nums.size()-1 반복문을 돌린다. 마지막으로 가장 안쪽에 작은 반복문은 k=j+1~nums.size() 반복문을 돌린다. 이렇게하면 가장 안쪽의 반복문에서 nums[i], nums[j], nums[k]를 이용하면 벡터 안에 모든 수 중 3개를 중복없이 고를 수 있다. 필요한 건 세 수의 합이므로 nums[i]+nums[j]+nums[k]을 이용해 이 수가 소수인지 판별한다.
소수임을 판별하기 위해 is_prime_num(int num) 함수를 만들어서 사용한다. 우선 2는 소수로 먼저 분리해준다. 2가 아닌 나머지의 수는 반복문을 이용해 소수임을 판별한다. for문을 이용해 2부터 num-1까지의 수로 num을 나누어 나머지를 확인한다. 나누어 떨어진다면 false를 반환해 소수가 아님을 나타내고 반복문이 돌아가는 동안 나누어 떨어지는 수가 없으면 마지막에 true를 반환해 소수임을 반환한다.
반복문의 안에서 is_prime_num을 이용해서 소수인지 확인하고 소수일 경우 answer++을 하여 수를 업데이트 한다. 소수가 아닐 경우 아무 것도 하지 않는다.
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/12977?language=cpp
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
'Code KATA > 알고리즘 코드카타' 카테고리의 다른 글
[2025.01.30] 기사단원의 무기 (0) | 2025.01.31 |
---|---|
[2025.01.29] 덧칠하기 (0) | 2025.01.29 |
[2025.01.07] 모의고사 (0) | 2025.01.27 |
[2025.01.24] 2016년 (1) | 2025.01.24 |
[2025.01.23] 명예의 전당 (1) (1) | 2025.01.23 |