프로그래머스_완전탐색_피로도[C++]

[문제링크]

[C++ 순열 구현]

직전에 올렸던 순열 알고리즘을 적용해보는 문제이다.

vector<int> v;
int solution(string numbers) {
    for(char c : numbers){
        v.push_back(c-'0');
    }
    return answer;
}

우선 먼저 solution 함수의 인자인 numbers를 숫자 단위로 split하여 v에 넣어줬다. v를 전역변수로 선언한 이유는 순열을 구하는 dfs함수에서 쉽게 접근 가능하도록 하기 위함이다.

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

소수 판별하는 함수도 따로 작성해줬다.
그리고 대망의 dfs코드를 보자.

unordered_set<int> checked; //중복된 조합이 있나 체크
void dfs(vector<int>& out, vector<bool>visited,int depth){
    if(depth==0){
        int sum = 0; //out에 있는 원소들을10진수로 변환
        int dx = 1;
        for(int i=out.size()-1;i>=0;i--){
            if(i==0 && out[i]==0)
                continue;
            sum += dx *out[i];
            dx *=10;
        } 
        if(checked.count(sum)) return; //중복여부 체크
        checked.insert(sum);
        bool flag =is_prime(sum);
        if(flag) answer++;
        return;
    }
    else{
        for(int i=0;i<v.size();i++){
            if(!visited[i]){
                visited[i] = true;
                out.push_back(v[i]);
                dfs(out,visited,depth-1);
                out.pop_back();
                visited[i]= false;
            }
        }
    }
}

처음 문제를 풀때 중복 체크를 안해줘서 계속 오답이 나왔다. 예를 들어 [0,1,1]이 들어왔고, r이 3일때 (1,0,1)이 두번 체크되고 결론적으론 count가 두번 증가하는 오류가 발생했다.이를 방지하기 위해 unordered_map을 이용하여 소수 판별하기 전에 중복을 체크를 해줌으로써 해결했다!

전체코드는 다음과 같다.

#include <string>
#include <vector>
#include<unordered_set>
using namespace std;
vector<int> v;
unordered_set<int> checked;
int answer = 0;
bool is_prime(int num){
    if(num<2)
        return false;
    for(int i=2;i<num;i++){
        if(num % i ==0) return false;
    }
    return true;
}
void dfs(vector<int>& out, vector<bool>visited,int depth){
    if(depth==0){
        int sum = 0;
        int dx = 1;
        for(int i=out.size()-1;i>=0;i--){
            if(i==0 && out[i]==0)
                continue;
            sum += dx *out[i];
            dx *=10;
        }
        if(checked.count(sum)) return;
        checked.insert(sum);
        bool flag =is_prime(sum);
        if(flag) answer++;
        return;
    }
    else{
        for(int i=0;i<v.size();i++){
            if(!visited[i]){
                visited[i] = true;
                out.push_back(v[i]);
                dfs(out,visited,depth-1);
                out.pop_back();
                visited[i]= false;
            }
        }
    }
}
int solution(string numbers) {
    for(char c : numbers){
        v.push_back(c-'0');
    }
    for(int i=1;i<=v.size();i++){
        vector<int> out;
        vector<bool>visited(v.size(),false);
        dfs(out,visited,i);
    }
    return answer;
}