[Programmers] Lv1)소수 만들기

Programmers Lv1) 소수 만들기

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12977

Summer/Winter Coding(~2018)에 수록된 문제로, 프로그래머스의 레벨1에 해당하는 문제입니다. 또한 문제는 C++로 풀이되었습니다

문제 풀이

• 문제에서 해결해야 하는 요점은 다음과 같습니다.

  1. 주어진 숫자의 리스트 (vector)에서 세 개의 숫자의 합의 모든 경우를 추출할 것.
  2. 각각 경우가 소수에 해당하는지 체크하고 이를 저장할 것.

1. 주어진 숫자의 리스트에서 세 개의 숫자의 합의 모든 경우를 추출하기

• 세 개의 숫자의 합의 모든 경우를 구해야 하고, 모든 경우를 구해야 하기 때문에 Brute Force 방법론을 사용, 3중 반복문으로 세 숫자를 선택할 수 있습니다.

  for (int i=0;i<size-2;i++) {
        for (int j=i+1;j<size-1;j++) {
            for (int k=j+1;k<size;k++) {
                int sum = nums[i] + nums[j] + nums[k];
                …
            }
        }
    }

2. 각각 경우가 소수에 해당하는지 체크하고 이를 저장할 것

• 소수를 판별하는 방법에는 다양한 방법이 있습니다. (에라토스테네스의 체 등) 현재 문제에서 시간 복잡도에 대한 특별한 제약이 없기 때문에, 소수를 판별하는 함수를 하나 구현해서 풀이하는 것이 간편합니다.
• k라는 숫자가 소수인지 판별하기 위해서 2부터 k-1까지의 숫자로 k라는 수를 전부 나누어봅니다. 만약 한 번이라도 나누어 떨어 지는 경우가 있다면 해당 숫자는 소수가 아니기 때문에 return false를 실행하고, 함수의 하단에는 return true 구문을 삽입합니다.

  bool checkPrime (int k) {
    for (int i=2;i<k;i++) 
        if (k % i == 0) return false;
    return true;
  }

전체 코드

#include <vector>
#include <iostream>
using namespace std;

bool checkPrime (int k) {
    for (int i=2;i<k;i++) 
        if (k % i == 0) return false;
    return true;
}

int solution(vector<int> nums) {
    int answer = 0;
    int size = nums.size();

    for (int i=0;i<size-2;i++) {
        for (int j=i+1;j<size-1;j++) {
            for (int k=j+1;k<size;k++) {
                int sum = nums[i] + nums[j] + nums[k];
                if (checkPrime(sum)) answer++;
            }
        }
    }
    return answer;
}

algorithm/소수 만들기.cpp at main · wkazxf/algorithm · GitHub