[프로그래머스 lv2] 소수 판별 (c++)

문제

---

 

 

풀이

---

 

numbers의 길이가 7 이하이니, 완전 탐색을 고려할 수 있다. numbers에서 몇 개 뽑아 나열해서 숫자를 만든다는 것은 순열을 떠올리게 만든다.

 

 

numbers가 최대 7자이니 순열 공식 7 * 6 .. 2 * 1 = 2520인데, 만약 소수 판별 부분에서 2부터 나눠가는 방식을 사용한다면 어떻게 될까? 7자리면 숫자 크기가 1000000을 넘어갈 수 있는데, 이러면 2520 * 1000000 = 2520000000으로 시간 초과가 발생할 위험이 있다.

 

즉 소수를 구하는 식을 에라토스테네스 체를 이용해야한다.

 

순열을 구하는 방식은 재귀함수를 이용한 완전 탐색을 이용하거나, c++에서 제공하는 next_permutation이 있다. 

 

 

 

코드

---

#include <bits/stdc++.h>

using namespace std;


vector<int> check;
set<int> st;

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

 

 

 

check는 순열을 구하기 위해 만들었다. 이는 중복으로 문자를 선택하지 않도록 하기 위함이다. set은 011과 11같이 두 번 생길 수 있지만 같은 값을 처리하기 위한 자료구조로, 중복값을 허용하지 않는 특징을 이용했다.

 

 

isPrime 함수는 소수 판별을 위한 것으로, n이 소수인지 아닌지 체크한다. 2부터 n까지 다 체크하는 게 아니라, sqrt(n)을 통해 제곱근 까지만 체크해 시간 복잡도를 줄인다.

 

 

void permu(int len, string numbers, string v){
    if(v.size() == len){
        int tmp = stoi(v);
        
        if(isPrime(tmp))
            st.insert(tmp);
    }
    else{
        for(int i = 0; i < numbers.size() ;i++){
            if(!check[i]){
                check[i] = true;
                //v += numbers[i]
                permu(len, numbers, v + numbers[i]);
                check[i] = false; 
                //v.erase();
            }
        }
    }
}

 

permu함수는 재귀 함수로 순열을 구하기 위한 함수다. check[i]가 false라는 건 아직 사용하지 않은 문자니 선택할 수 있음을 나타낸다. 

 

여기서 나는 추가로 v += numbers[i]후 v에서 다시 빼는 코드도 있었는데, 그러면 erase과정에서 오류가 생길 확률도 있고 디버깅하기 골치아팠었다. 위 처럼 매개변수에 v + numbers[i]를 하면, 그런 작업이 필요가 없어 편하다는 사실을 알 수 있었다. 

 

재귀 함수 사용 시 이렇게 매개변수에 합을 구해 넣는 방법을 잘 배울 수 있었다.

 

int solution(string numbers) {
    int answer = 0;
    int n = numbers.size();
    string v = "";
    check.resize(n, false);
    
    for(int i = 1; i <= n ;i++)
        permu(i, numbers, v);
    
    return st.size();
}

 

 

마지막 solution부분이다. resize를 이용해 전역으로 선언한 check를 초기화한다. 

 

 

 

풀고 보니 next_permutation을 이용해 풀이한 방법도 존재했다.

 

 

do {
      string tmp;
      for(int i = 0; i < numbers.size(); ++i)
      {
          tmp += numbers[i];
          int c = stoi(tmp);
          if(isPrime(c)) 
              st.insert(c);     
      }
} while (next_permutation(v.begin(), v.end()));

 

next_permutation은 이런식으로 많이 작성하는 것 같다. next_permutation(v.begin(), v.end()) 같이 특정 배열이나 iterator를 넣을 수 있고, 이후 실행하면 이 배열 안의 요소로 다음 순서의 순열을 반환한다.가령 1, 2, 3 으로 v가 이루어져있다면 그 다음 1, 3, 2가 되는 식이다. 

 

순열을 생성하는 걸 성공하면 true, 아니면 false를 반환한다. 

 

이걸 사용할 때 주의할 점은 다음과 같다.

 

1. next_permutation()안에 들어가는 배열이 오름차순으로 정렬되어있어야 한다. 

 

2. 만약 배열에 중복되는 원소가 있다면 중복되는 순열을 무시하고 순열을 생성한다. 예로  1, 2, 2 가 있을 때  

 

{1, 2, 2} , {2, 1, 2}, {2, 2, 1} 이렇게만 생성한다는 것이다.

 

 

이렇게 순열 구현 방법 두 가지를 알아봤다. 앞으로 잘 사용해봐야겠다.