문제

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

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

제한 사항

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

예제

예제 입력
numbers
"17"
"011"

예제 출력
3
2

접근

  • 소수를 어떻게 찾을 것인가?
  • 만들 수 있는 숫자들은 어떻게 찾아낼 것인가?

내가 생각한 풀이

  • 소수를 찾는 방법으로는 에라토스테네스의 체를 활용했다. worst case가 1000만이라 시간 초과가 우려되긴 했지만 계산해보니 충분히 괜찮다고 판단했다.
  • worst case만큼 경우의 수를 돌려보기로 했다. 예를 들어 숫자 2개가 주어지면 나올 수 있는 worst case는 99이고 숫자가 4개 주어지면 9999가 된다. 이를 활용하여 숫자의 갯수에 대해 worst case만큼의 모든 경우의 수를 다 따져봤다.
  • for문을 돌면서 이 숫자를 만들 수 있나 없나 판단한다. 예를 들어 주어진 수가 17이고 for문의 수가 13이라면 1과 7이 하나씩 있다는 배열의 정보를 가지고 다른 배열과 비교한다. 1은 17에서 하나를 사용 할 수 있으니 넘어가고 3은 비교를 해봤을 때 사용하지 못하기 때문에 넘어간다.

미처 생각하지 못했던것

  • C++에서는 이미 이런 상황에 대해 아주아주아주 좋은 함수를 제공하고 있었다. 그 이름하여 next_permutation! algorithm 헤더 파일에 내장되어 있는 함수이며 숫자가 주어졌을 때 그 숫자로 만들 수 있는 모든 경우의 수를 알아서 찾아준다. 이걸 알았더라면 훨씬 효율적인 코드를 짤 수 있었을 것이다. 좋은 정보 알려준 시형이형 고마워요… (다시 한 번 느끼는 코드리뷰 및 피드백의 중요)

코드

#include <string>
#include <vector>
#include <cmath>
using namespace std;

int solution(string numbers) {
  //count는 기존 넘버의 사용 가능한 숫자들을 저장하는 배열, sosoo는 소수인 수를 체크하는 배열
  int answer = 0, count[10] = {0, }, arr[7] = {0, }, sosoo[10000001] = {0, };
  //arr라는 배열을 사용해 numbers를 int형으로 저장함과 동시에 숫자들을 count한다.
  for(int i = 0 ; i<numbers.size(); i++)
  {
      arr[i] = numbers[i] - '0';
      count[arr[i]]++;
  }
  //에라토스테네스의 체를 사용하는 과정
  for(int i = 2 ; i<=sqrt(10000000) ; i++)
  {
      for(int j = i+i ; j<10000000 ; j += i)
          sosoo[j] = 1;
  }
  //for문의 범위를 10의 n승 단위로
  for(int i = 2 ; i<pow(10,numbers.size()) ; i++)
  {
      string temp = to_string(i);
      int tempcount[10] = {0, }, tc = 0, flag = 0;
      //tempcount는 for문을 돌리며 나온 숫자에 대해 사용가능한 숫자를 카운트 하기 위한 배열
      for(int j = 0 ;j<temp.size(); j++)
      {
          tempcount[temp[j]-'0']++;
      }
      for(int j = 0 ;j<10;j++)
      {
          //만약 tempcount에서 사용한 숫자가 입력으로 주어진 것보다 크면 이 숫자는 사용 불가능
          if(tempcount[j]>count[j]){
              flag = 1;
              continue;
          }
      }
      if(flag != 1)
      {
          //위의 조건을 충족했을 때 소수라면 answer를 증가시킨다.
          if(sosoo[i] == 0){
              answer++;
          }
      }
  }
  return answer;
}