[프로그래머스][C++] 소수 찾기 (Level2)

문제 링크:

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

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

 

 

문제 설명

 

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

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

 

 

---

문제 해결

 

이 문제는 간단하게 완전탐색으로 푸는 문제였다.

 

입력으로 받은 문자열로부터 0~9까지의 숫자가 몇 개씩 있는지 배열에 저장한 후, 배열의 값이 0보다 큰 경우 재귀 함수를 통해 탐색하는 방식으로 해결하였다. 이러한 로직을 다음의 두 가지 함수로 구현하였다.

• 소수 판별 함수 (isPrime)
• 탐색하면서 가능한 숫자를 만들어주는 함수 (make)

해결 방법이 어렵지 않고 level2인 만큼 무난한 난이도라 큰 어려움은 없었지만, 구현 시 신경써야 할 부분이 있다면 입력 문자열로부터 새로운 숫자 문자열을 만드는 부분과 문자열을 숫자로 변환해주어야 하는 부분이었던 것 같다.

 

 

---

소스코드

 

#include <string>
#include <vector>
using namespace std;
int num[10] = {0, };
int ans = 0;

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

void make(string now, int arr[10]) {
    int copy[10];
    int last = now.back()-'0';
    for(int i=0; i<10; i++)
        copy[i] = arr[i];
    copy[last]--;

    int nowNum = 0;
    for(int i=0; i<now.length(); i++)
        nowNum = nowNum * 10 + (now.at(i)-'0');

    if(nowNum >= 2 && isPrime(nowNum))
        ans++;

    for(int i=0; i<10; i++){
        if(copy[i] > 0)
            make(now + char(i+'0'), copy);
    }
}

int solution(string numbers) {
    int len = numbers.length();
    for(int i=0; i<len; i++) {
        int n = numbers.at(i)-'0';
        num[n]++;
    }

    for(int i=1; i<10; i++){
        if(num[i] < 1) continue;
        string tmp;
        make(tmp+char(i+'0'), num);
    }
    return ans;
}

 

깃허브:

https://github.com/jihyehann/PS/blob/main/programmers/42839/42839.cpp