[프로그래머스/C++] 소수 찾기 풀이

프로그래머스 : 소수 찾기

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기 | 프로그래머스

---

문제

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

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

 

제한사항

numbers는 길이 1 이상 7 이하인 문자열입니다.

numbers는 0~9까지 숫자만으로 이루어져 있습니다.

013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다

 

---

이 문제를 풀어보기 전에 백준 - 소수 구하기 문제를 풀어보면 좋다.

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

이 문제는 아리스토테네스의 체 를 사용해서 풀어야 하는 문제다.

아리스토테네스의 체란? 👇

https://silver-g-0114.tistory.com/39?category=1094593

[Algorithhm] 에라토스테네스의 체 알고리즘이란?

 

먼저 입력된 numbers 를  내림차순 정렬해 numbers를 조합해 만들 수 있는 가장 큰 수를 만든 후 2부터 가장 큰 수 까지 차례대로 소수인지 아닌지 검사한다. (에라토스테네스의 체 를 사용)

 

이 때 checknumbers 메소드로 입력된 numbers 로 만들 수 있는 소수인지 검사한다.

일의 자리부터 탐색을 시작해서 visit배열로 사용한 수인지 아닌지 검사한다.

 

간단해 보이지만 제대로 이해하는 데 정말 오랜 시간이 걸렸다 ㅠㅠ 

---

풀이

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

using namespace std;

bool checknumber(int i, string numbers){ // i가 numbers로 만들 수 있는 소수인지 판별
    bool flag = false;
    vector<bool> visit(numbers.length());
    
    while(i != 0){
        flag = false;
        int tmp = i%10; // 일의 자리부터 탐색 시작
        for(int j=0; j<=numbers.length(); j++){
            if(tmp==numbers[j]-'0' && visit[j]==0){ // numbers의 숫자인지 판단 && 방문 판단
                flag = true;
                visit[j] = 1;
                break;
            }
        }
        if(flag==false){
            return false;
        }
        i /= 10;
    }
    return true;
}

int solution(string numbers) {
    int answer = 0;
    
    // 내림차순 -> numbers 의 큰 수 만듦 (2~71) 소수 찾기
    sort(numbers.begin(), numbers.end(), greater<int>()); 

    vector<bool> tmp(stoi(numbers)+1);
    
    for(int i=2; i<=stoi(numbers); i++){
        if(tmp[i] == false && checknumber(i, numbers)){
            answer++;
        }
        if(tmp[i] == false){ // i의 배수는 모두 소수가 아님을 표시
            for(int j=i; j<=stoi(numbers); j+=i){
                tmp[j] = true;
            }
        }
    }

    return answer;
}

 

---

풀이 인증