[프로그래머스] 소수 찾기 c++ (완전탐색, 에라토스테네스의 체)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

풀이

완전탐색 문제이며, 조합 / 중복제거 / 에라토스테네스의 체를 활용하여 해결하였다.

---

해결한 방법은 다음과 같다.

 

1. 종이 조각으로 만들 수 있는 모든 경우의 수 구하기 (next_permutation 활용)

2. 경우의 수에서 중복 제거하기 (erase, unique 활용)

3. 소수 판별하기

 

1.  모든 경우의 수 구하기

모든 경우의 수는 c++ algorithm 헤더파일의 함수인 next_permutation 을 활용하였다.

next_permutation: 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없을 경우(다음에 나온 순열이 순서상 이전 순열보다 작을 경우) false를 반환한다.

즉 1-2-3 이라는 배열이 있을 때, next_permutation 사용 시 배열 값이 1-3-2 (다음 순열) 로 바뀌고 true를 반환한다.

(보통 do-while 문과 활용하는 경우가 많다.)

 

아래 예제를 통해 확인해 보자.

// #include <algorithm> 필요!
vector<int> v;
    
v.push_back(1);
v.push_back(2);
v.push_back(3);
    
do{
	for(int i = 0; i < 3; i++){
		cout << v[i] << " ";
	}
	cout << '\n';
}while(next_permutation(v.begin(),v.end()));

 

출력은 순열 순서대로

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

이 출력된다.

 

이렇게 처음 입력받은 문자열을 char 벡터에 각각 저장해 주고 정렬 후, next_permutation을 활용하여 모든 경우의 수를 저장시켰다.

    int answer = 0;
    vector<char> v;
    vector<int> toNum;
    // 각각 문자 저장
    for(int i = 0; i < numbers.length(); i++) v.push_back(numbers[i]);
    sort(v.begin(), v.end()); // next_permutation 활용 위해 정렬
    
    do{
        string str = "";
        for(int i = 0; i < v.size(); i++){
            str.push_back(v[i]);
            toNum.push_back(stoi(str));
        }
    }while(next_permutation(v.begin(), v.end()));

2.  경우의 수에서 중복 제거하기

이렇게 열심히 경우의 수를 구했지만, 문제가 하나 남아 있다. 바로 중복된 수가 있다는 것이다!

 

문제에도 나와있듯이

• 11과 011은 같은 숫자로 취급합니다.

이렇게 중복되는 수를 제거하기 위해서 erase와 unique 함수를 사용했다.

unique
- algorithm 헤더에 존재
- vector 배열에서 중복되지 않는 원소들을 앞에서부터 채워나가는 함수이다.
- 중복되지 않는 원소들을 앞에서부터 채워나가는 역할을 하기때문에 남은 뒷부분은 그대로 vector 원소 값이 존재한다.
- 자신이 바꾼 vector의 end() 부분을 반환

 

예시를 통해 알아보자.

1 2 2 3 5 5 6 이 들어가있는 vector가 있다고 하자.

맨 처음 1은 중복이 없으므로 그대로이고

그 다음 2도 아직 중복이 없으므로 그대로 1 2 2 3 5 5 6 이다.

 

그러나 3번째 2는 이전에 2가 있었으므로 그 자리에 중복되지 않는 원소 3을 채운다.

1 2 2 3 5 5 6 → 1 2 3 3 5 5 6

 

다음 3 역시 중복이므로 5를 채우고, 그 다음 5역시 6을 채운다.

1 2 3 3 5 5 6 → 1 2 3 5 5 5 6

1 2 3 5 5 5 6 → 1 2 3 5 6 5 6

 

그 후 남은 뒷부분은 그대로 vector 원소 값이 존재하게 된다.

1 2 3 5 6 5 6

(바뀌지 않는 시작 부분인 5를 반환한다.)

 

이 unique 함수를 erase 함수와 연계하여 중복을 제거할 수 있다.

erase
- vector에서 특정 원소를 삭제하는 함수
- v.erase(v.begin() + index); // 해당 index 원소 삭제
- v.erase(v.begin() + a, v.begin() + b); // s에서 e 까지 원소 삭제

 

위 예제에서 erase 함수의 시작 범위를 5로 한다면 중복이 제거 될 것이다.

(unique 함수의 반환 부분이므로 unqiue 반환 값을 넣어주면 된다!)

 

따라서 중복을 제거하는 코드는 아래와 같다.

v.erase(unique(v.begin(), v.end()), v.end());

 

설명이 길어졌는데...다시 문제로 돌아오자!

결국 경우의 수에서 중복을 제거하면 된다.

unique를 실행하기 위해 정렬을 해주고 erase를 해주면 된다!

sort(toNum.begin(), toNum.end());
toNum.erase(unique(toNum.begin(), toNum.end()), toNum.end());

3.  소수 판별하기

소수 판별은 에라토스테네스의 체를 이용하였다.

(소수 관련 문제를 풀 때 자주 사용하므로 알아두자!)

 

에라토스테네스의 체
- 2부터 n까지의 수 중에 소수를 판별하기 위한 알고리즘
- 소수를 찾으면 해당 수의 배수를 모두 지워나가는 방식

 

에라토스테네스의 체

 

여기서 팁은, 소수 판별을 2부터 n까지 모두 확인할 필요가 없다는 것이다!

n의 제곱근까지만 확인하면 된다.

소수는 n의 배수가 아니다.
입력받은 수를 입력받은 수보다 작은 수 들로 나누어서 떨어지면 소수가 아니다.
따라서 모두 나누어볼 필요없이, 루트 n 까지만 나누어서 떨어지면 소수가 아니다.

 

제곱근은 sqrt 함수를 사용하면 된다.

sqrt
- math.h 헤더에 존재
- sqrt(121) = 11

코드는 아래와 같다.

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

 

이렇게 소수일 경우 answer에 더해주면 정답을 구할 수 있다!

---

코드

알고리즘을 하나하나 설명하다 보니 글이 길어졌는데, next_permutation / unique / erase 와 같은 함수들을 활용하면 코드도 간결하고 효율적으로 구현할 수 있다.

#include <string>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

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

int solution(string numbers) {
    int answer = 0;
    vector<char> v;
    vector<int> toNum;
    
    for(int i = 0; i < numbers.length(); i++) v.push_back(numbers[i]);
    sort(v.begin(), v.end());
    
    do{
        string str = "";
        for(int i = 0; i < v.size(); i++){
            str.push_back(v[i]);
            toNum.push_back(stoi(str));
        }
    }while(next_permutation(v.begin(), v.end()));
    
    sort(toNum.begin(), toNum.end());
    toNum.erase(unique(toNum.begin(), toNum.end()), toNum.end());
    
    for(int i = 0; i < toNum.size(); i++)
        if(isPrime(toNum[i])) answer++;
    
    return answer;
}