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

문제

 

<문제 설명>

 

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

 

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

 

 

<제한사항>

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

 

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

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

 

 

 

문제 풀이

 

다음의 문제를 순서대로 해결해서 문제를 풀었습니다. 

1. 종이 조각으로 만들 수 있는 모든 경우의 수 구하기

2. 모든 경우의 수에서 중복된 수 제거하기

3. 남은 수 중에서 소수 판별하기

 

 

1. 종이 조각으로 만들 수 있는 모든 경우의 수 구하기

가지고 있는 종이 조각의 모든 순열에 대해서, 1부터 종이 조각의 수까지의 조합을 구했습니다. 

 

ex) numbers = "012"인 경우

    순열 1) "012"

         "0", "01", "012" 저장

    순열 2) "021"

         "0", "02", "021" 저장

      .

      .

      .

    순열 6) "210"

         "2", "21", "210" 저장

 

 

 

 

2. 모든 경우의 수에서 중복된 수 제거하기

1과 같은 방법으로 경우의 수를 구할 경우, "02"와 "2"은 사실 2이라는 같은 수입니다. 따라서 vector 내의 중복을 없애기 위해 erase와 unique를 사용했습니다. 

 

vector<int> v = { 1, 2, 3, 1, 2 };
sort(v.begin(), v.end());	// 11223
unique(v.begin(), v.end());	// 12323

위와 같이 정렬된 벡터에서 unique를 사용하게 되면 중복되지 않은 값을 앞쪽으로 보내고, 뒤쪽에는 쓰레기 값들을 저장하게 됩니다. 그리고 unique는 제일 처음 나오는 쓰레기 값의 iterator를 반환합니다.(여기선 v[3], 즉 두 번째 나오는 2를 가리킵니다.)

 

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

따라서 위와 같은 코드를 작성하면, 벡터에서 필요 없는 값들은 삭제하고 중복 없는 데이터를 얻을 수 있습니다. 

 

 

 

 

3. 남은 수 중에서 소수 판별하기

소수를 판별하기 위해 에라토스테네스의 체를 이용하였습니다. 에라토스테네스의 체를 간단히 설명하자면, 2부터 n까지의 수 중에 소수를 판별하기 위한 알고리즘입니다. 간단하게 설명하자면, 소수를 찾으면 해당 수의 배수를 모두 지워나가는 방식입니다. 자세한 설명은 링크에 나와있습니다. 

 

에라토스테네스의 체

 

 

 

 

소스코드

// 소수 찾기
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <math.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 = "";
        // 만들 수 있는 모든 숫자 nums에 저장
        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++)
        // 소수일 경우 answer++
        if (isPrime(nums[i]))
            answer++;

    return answer;
}

 

 

 

 

 

 

공부한 것을 정리한 내용입니다. 수정할 부분이 있다면 알려주시면 감사하겠습니다 :)