[프로그래머스] 42839번 소수 찾기 C++

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

 

메모

- 소수인지 판별할 때 에라토스테네스의 체 사용

- stoi

  https://velog.io/@haminggu/C-%EB%AC%B8%EC%9E%90%EC%97%B4-%EC%B2%98%EB%A6%AC-%ED%95%A8%EC%88%98-cstr-atoi-stoi-%ED%8A%B9%EC%A7%95%EA%B3%BC-%EC%82%AC%EC%9A%A9%EB%B2%95

[C++] 문자열 처리 함수 c_str(), atoi(), stoi() 특징과 사용법

 

- vector 중복 제거

  https://dpdpwl.tistory.com/39

[C++]벡터 중복제거(sort,unique,erase)

- unique는 연속된 중복 원소를 쓰레기값으로 판별해서 vector의 가장 끝 부분으로 보냄. (정확한 이동이 이게 맞는지는 모르겠음)

  중복되지 않는 값만 vector의 앞쪽으로 보냄.

- unique가 끝났으면 반환되는값은 vector의 쓰레기값의 첫번째 위치가 됨

  v.erase(unique(s.begin(),s.end()),s.end());

- next_permutation에서 permutation은 순열, 그니까 확통에서 3P2 할 때 그 P

  https://taehun0933.tistory.com/18

 

 

 

맞힌 코드

#include <bits/stdc++.h>

using namespace std;

bool isPrime(int n) {
    if (n<2)
        return false;

    for (int i=2; i<=sqrt(n); i++){
        if (n%i == 0)
            return false;
    }
    return true;
}

int solution(string numbers){
    int answer = 0;
    vector<char> v;  // 종이 조각의 각 숫자
    vector<int> nums;
    
    // numbers의 각 숫자를 v에 입력 후 오름차순 정렬
    for (int i=0; i<numbers.size(); i++){
        v.push_back(numbers[i]);
    }
    
    sort(v.begin(), v.end());

    do {
        string temp = "";
        
        // 만들 수 있는 모든 수
        for (int i=0; i<v.size(); i++) {
            temp.push_back(v[i]);
            nums.push_back(stoi(temp));
        }
    } while (next_permutation(v.begin(), v.end()));

    // 중복 값 없애기
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    
    for (int i=0; i<nums.size(); i++){
        // 소수인 경우
        if (isPrime(nums[i]))
            answer++;
    }
    return answer;
}

 

 

참고)

https://mjmjmj98.tistory.com/50

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

 

https://beankong-devlog.tistory.com/48

프로그래머스 / level.2 / 소수 찾기(C++)