✍️Today I Learned

📅 2025-08-12

• 프로그래머스 - 소수 찾기
• 팀플 - 중간 보스, Swarm 몬스터 만들기. 공격 어빌리티 만들기

프로그래머스 - 소수 찾기

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

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

제한사항

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

풀이

완전 탐색 방식으로 해결했다. 조합한 문자열 중 소수인 경우에만 int로 변환하여 벡터에 넣고 중복을 없애 총 개수를 return했다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
// 소수인지 확인하는 함수
bool IsPrime(int num)
{
    if (num<2) return false;
    int i=2;
    while(i*i<=num)
    {
        if(num%i==0) return false;
        i++;
    }
    return true;   
}
// 찾은 소수를 벡터에 저장하는 함수
void findPrime(string& numbers, vector<bool> used, string num, vector<int>& primenums)
{
    for(int i=0; i<numbers.size(); i++)
    {
        if(used[i]) continue;
        
        num+=numbers[i];
        used[i] = true;
        
        if(IsPrime(stoi(num))) primenums.push_back(stoi(num));
        findPrime(numbers, used, num, primenums);
        
        used[i] = false;
        num.pop_back();
    }
}

int solution(string numbers) {
    int answer = 0;
    vector<bool> used(numbers.size(), false); 
    vector<int> primenums;
    
    findPrime(numbers, used, "", primenums);
    
    // 중복 제거
    sort(primenums.begin(), primenums.end());
    primenums.erase(unique(primenums.begin(), primenums.end()),primenums.end());
    
    answer = primenums.size();
    return answer;
}

---

💡 느낀 점 (What I Felt)

알고리즘 훈련을 더 많이 해야하는데...

---

출처 프로그래머스: 소수 찾기