프로그래머스 42893 - 소수 찾기 (c++)

프로그래머스 42893 - 소수 찾기

문제 링크

생각 및 접근

• 문제부터 소수 찾기. 그렇다면 소수를 체크하는 함수를 작성해야 했다.

    bool chkPrime(int a){
        if(a == 0 || a == 1)  return false;
        for(int i = 2; i <= sqrt(a); i++){
            if(a % i == 0)  return false;
        }
        return true;
    }

  • 함수를 더 최적화하기 위해서 i를 sqrt(a)까지 돌게 했다.

    • 왜? (출처 : Coding Monster님의 OpenTutorials )

        양의 정수 n, a, b에 대해 n = a * b (단, a <= b) 라고 해봅시다. 그러면 a와 b는 n의 약수가 됨을 알 수 있습니다. 
      
        a와 b의 값을 생각해봅시다. a의 최소값은 1이 되며, 이 때 b는 n이 됩니다.
        위의 식이 성립하기 위해서는 a가 점점 커질수록 b는 작아져야 하는 반비례 관계임을 알 수 있습니다. 
      
        위의 식 n=a*b에서 약수 a가 존재하면, 곱해서 n이 되는 짝 b가 항상 존재합니다.
        즉, 모든 약수는 곱해서 n이 되는 쌍이 존재하며, (a, b) 꼴 쌍에서 a <= b라고 할 경우 a의 최대값은 sqrt(n)가 됩니다. 
      
        그 이유는 a <= b 가 성립하는 상태에서 a가 가장 커질 수 있는 경우는 a == b인 경우이고, 이는 n = a * a 꼴이 됩니다.

• string numbers의 숫자들을 하나씩 분리해서 다시 붙이는 작업을 해주어야 하는데, 이를 next_permutation으로 해결하였다. next_permutation를 통해서 나온 배열을 i = 1 .. numbers.size()까지 돌면서 substr 함수를 이용해 0번부터 i개의 string을 잘라낸다. 잘라낸 string을 소수 체크를 하고, 미리 선언해둔 map<int, int> m에 추가시킨다.

  • next_permutation란? 링크
    • 배열을 보고, 조합에 의한 순서대로 순회한다. 내림차순으로 정렬이 될 때까지 반복한다.
  • next_permutation를 사용할 때
    • 배열은 오름차순으로 정렬되어 있어야 한다.

코드

#include <bits/stdc++.h>
using namespace std;

bool chkPrime(int a){
    if(a == 0 || a == 1)  return false;
    for(int i = 2; i <= sqrt(a); i++){
        if(a % i == 0)  return false;
    }
    return true;
}

int solution(string numbers) {
    int answer = 0, size = numbers.size();
    map<int, int> m;
    sort(numbers.begin(), numbers.end());

    do{
        for(int i = 1; i <= size; i++){
            string _temp = numbers.substr(0, i);
            int temp = stoi(_temp);
            if(m[temp] == 0 && chkPrime(temp)){
                m[temp]++;
            }    
        }
    }while(next_permutation(numbers.begin(), numbers.end()));

    for(auto k : m){
        if(k.second != 0)
            answer++;
    }
    return answer;
}

채점 결과