[프로그래머스] Summer/Winter Coding(~2018) > 소수 만들기

요즘 푼 문제 중에는 소수 관련 문제가 많아서
이걸 또 할까말까 하다가 소수 만드는 코드는 절대 까먹지 말자 싶어서 한 번 풀어봤다.

근데 보통 소수를 만드는 데에서 끝나지 않고 이 문제처럼 소수를 활용하게끔 하는 것 같다.

이 문제에서도 소수 알고리즘보다는 숫자 배열 중 3개의 조합을 어떻게 만들 것인지가 더 중요한 거 같긴하다..!

나는 보조 배열의 순열을 통한 조합을 이용했다

만약 5개의 숫자 배열 중 3개의 숫자를 뽑아 조합을 만든다고 했을 때 다음과 같은 과정을 거친다.

1. 조합을 위한 보조 배열을 만든다.
   - 0과 1로 이루어져있어야 하고, 0이 앞에 와야 한다.
   - int subPermutation = [ 0, 0, 1, 1, 1 ];
2. 그리고 보조 배열에 대해 next_permutation 을 연속으로 호출하면서 나올 수 있는 모든 경우의 수를 얻는다.
3. 이 때 1의 위치인 수를 원래 배열에서 뽑으면 그게 조합이 된다

원래 next_permutation을 쓰려면 sort를 해주어야 하는 것으로 알고 있는데, 여기에서는 처음 배열을 만들 때부터 0 먼저 넣고 그 다음 1을 채워서 따로 sort를 해주지 않았다.

배운 점

1. 보조 배열의 순열을 통해 조합 만드는 방법
2. vector와 array의 차이

보통 vector를 자주 쓰다가 여기에서는 처음으로?
array와 vector를 섞어서 썼다. 애초에 solution 함수의 인자가 vector로 들어와서 그런 것도 있지만..!

그 동안 별 고민없이 쓴 듯해서 한 번 그 차이를 알아보았다.

생성

• Vector: 요소들을 순차적으로 저장할 수 있는 컨테이너
• Array: 인덱스 기반 기본 자료구조

메모리

• Vector: 배열보다 메모리 공간을 더 차지함
• Array: 메모리 효율성 높음

길이(length)

• Vector: 동적으로 달라질 수 있음
• Array: 고정되어 있음

사용(Usage)

• Vector: 원소의 삽입과 삭제가 빈번한 경우. 단 중간에 삽입하거나 삭제가 많은 경우에는 비효율적
• Array: 원소를 조회할 일이 많은 경우. 조회에 드는 시간이 O(1)로 일정함

알아보고 나니 이 문제에서는 삽입과 삭제가 동적으로 이루어지지는 않으므로 array를 써도 괜찮은 것 같다.

// 소수 만들기 https://programmers.co.kr/learn/courses/30/lessons/12977
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

bool IsPrimeNumber(int num) {
    for(int i = 2; i <= num/2; i++) {
        if(num % i == 0) {  
            return false;
        }   
    }
    return true;
}

int solution(vector<int> nums) {
    // 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수
    int answer = 0;
    int numsSize = nums.size();

    // 1. 조합을 위한 보조 순열 만들기  
    int subPermutation[numsSize];
    for(int i=0; i<numsSize-3; i++) {
        subPermutation[i] = 0;
    }
    for(int i=numsSize-3; i<numsSize; i++) {
        subPermutation[i] = 1;
    }
    
    // 2. 소수의 개수 판단
    do {
        int sum = 0;
        for(int i=0; i<numsSize; i++) {
            // elem이 1이면 sum에 더해보고 소수이면 answer++
            if(subPermutation[i] == 1) {
                sum += nums[i];
            }
        }
        if(IsPrimeNumber(sum)) {
            answer++;
        }
    } while(next_permutation(subPermutation, subPermutation + nums.size()));

    return answer;
}