22) 프로그래머스 Lv2 - 소수 찾기

코딩테스트 연습 - 소수 찾기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

---

예외를 생각 못해서 오래 걸린 문제.

#include <bits/stdc++.h>

using namespace std;

int check_primNum[10000000] = {0, };
int check[7] = {0, };
string nums;
int answer = 0;
unordered_set<int> s;

void do_primNum(int N) {
    check_primNum[0] = 1;
    check_primNum[1] = 1;
    for(int i = 2; i < N; i++) {
        if(check_primNum[i] == 1) continue;
        for(int j = i+i; j < N; j += i) {
            check_primNum[j] = 1;
        }
    }
}

void make_numbers(string si_number, int cnt) {
    if(cnt != 0) {
        s.insert(stoi(si_number));
    }
    if(cnt == nums.length()) {
        return;
    }
    for(int i = 0; i < nums.length(); i++) {
        if(!check[i]) {
            check[i] = 1;
            si_number += nums[i];
            make_numbers(si_number, cnt+1);
            si_number.pop_back();
            check[i] = 0;
        }
    }
}

int solution(string numbers) {
    nums = numbers;
    do_primNum(pow(10, nums.length()));
    string si_number = "";
    make_numbers(si_number, 0);
    unordered_set<int>::iterator iter;
    for(iter = s.begin(); iter != s.end(); iter++) {
        if(check_primNum[*iter] == 0) {
            answer++;
        }
    }
    return answer;
}

1. "에라토스테네스의 체"를 활용해서 조건에 만족하는 가장 큰 값인 "9999999"까지의 수 중에 소수를 우선 걸러낸다.

2. 종이로 만들 수 있는 모든 수를 찾는다.

(여기서 실수 했던 점 : string si_number == "" 일 때 stoi(si_number)하면 core dump가 일어날 수 있다.)

3. 수 들을 전부 set에 넣고 마지막에 걸러낸 소수배열과 비교해서 답을 구한다.

 

구현 자체는 어렵다고 못느꼈지만 하나의 실수 때문에 시간을 너무 허비한 문제였다.