Programers : 소수 만들기

김정욱·2021년 2월 2일
0

Algorithm - 문제

목록 보기
84/249
post-custom-banner

소수 만들기

코드

[ 정답 풀이 ]

#include <vector>
#include <iostream>
#include <map>
#include <cmath>
#include <algorithm>
using namespace std;
/* 숫자 a가 소수인지 확인하는 함수 */
bool isPrime(int a){
    if(a < 2) return false;
    for(int i=2;i<=sqrt(a);i++) if(a % i == 0) return false;
    return true;
}
int solution(vector<int> nums) {
    int answer = 0;
    sort(nums.begin(), nums.end());
    /* 합으로 구할 수 있는 모든 수를 구하면서 바로 개수 count! */
    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++)
            {
                int sum = nums[i] + nums[j] + nums[k];
                if(isPrime(sum)) answer++;   
            }
    return answer;
}
  • 합이 어떤 경우의수로 나오느냐에 따라 개수를 count해야한다.

[ 문제 주의하기; ] - 오답

#include <vector>
#include <iostream>
#include <map>
#include <cmath>
#include <algorithm>
using namespace std;
bool isPrime(int a){
    if(a < 2) return false;
    for(int i=2;i<=sqrt(a);i++) if(a % i == 0) return false;
    return true;
}
int solution(vector<int> nums) {
    int answer = 0;
    map<int, int> m;
    sort(nums.begin(), nums.end());
    /* 합으로 구할 수 있는 모든 수를 구함 */
    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++)
            {
                int sum = nums[i] + nums[j] + nums[k];
                if(!m[sum])  m[sum]++;
            }
    /* 갯수 count! */
    for(auto it=m.begin();it != m.end();it++) 
        if(isPrime(it->first)) answer++;
    return answer;
}
  • 해당 코드는 오답이다 --> map을 사용해 중복으로 나오는 합은 1개로 생각했기 때문
  • 문제에서 이것과 관련된 근거가 없어서 조금 헷갈려했다.
  • sum이 같은 value가 나오더라도 조합의 경우가 다르면 갯수를 count 해야한다;
profile
Developer & PhotoGrapher
post-custom-banner

1개의 댓글

comment-user-thumbnail
2022년 2월 24일

감사합니다!
어쩌다 맞췄는데 왜 맞았는지 잘못 이해하고 있었는데 위 글보고 이해했습니다! :)

답글 달기