문제 42839. 소수 찾기

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

 

 

난이도 : Lv.2

 

문제 요약 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

입력

• 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers

입력 제한

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입력 예제

// input
"17"

// ans
3

 

풀이 방식

이 문제는 numbers라는 매개변수로 주어진 숫자 문자열을 통해 만들 수 있는 모든 숫자를 구한 다음, 소수의 개수를 구하면 된다. 따라서 짜야하는 코드 아래 2가지이다.

1. numbers를 통해 만들 수 있는 모든 문자열 구하기
2. 해당 숫자가 소수인지 구하기

각각을 따로 보면 1번은 완전탐색(DFS)으로, 2번은 에라토스테네스의 체를 이용하여 구하면 된다. 즉, 1번을 통해 숫자를 얻을 때마다 해당 숫자가 소수인지 판단하는 2번 코드를 호출하면 된다.

아래 정답 코드에서 1번은 dfs()로, 2번은 isPrime()이라는 이름의 함수로 구현하였다.

 

정답 코드 

#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <iostream>

using namespace std;

map<int, int> m1;
vector<bool> visited;
vector<int> v1;
string numbers_global;

int numbers_len;

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

int getAns(){
    int ans = 0;
       
    for(auto it : m1){
        
        if(isPrime(it.first)){
            //cout << it.first << '\n';
            ans++;
        }
    }
    
    return ans++;
}

void dfs(int k, int size){
    
    if(k == size){
        string s = "";
        for(int elem : v1){
            s += numbers_global[elem];
        }
        
        //cout << s << '\n';
        
        m1[stoi(s)]++;
        
        return;
    }
    
    for(int i = 0; i < numbers_len; i++){
        if(!visited[i]){
            v1.push_back(i);
            visited[i] = true;
            
            dfs(k, size+1);
            
            v1.pop_back();
            visited[i] = false;
        }
    }
    
    return;
}

int solution(string numbers) {
    int answer;
    
    numbers_len = numbers.length();
    visited.resize(numbers_len);
    numbers_global = numbers;
    
    for(int i = 1; i<=numbers_len; i++){
        dfs(i, 0);
    }
      
    answer = getAns();
    return answer;
}