프로그래머스 : 소수 찾기(lv2) C++

프로그래머스 링크

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

프로그래머스

문제 설명

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

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

제한사항

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

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

알고봐야할 함수 및 자료구조

next_permutation();

해당 함수는 #include <algorithm> 에 담겨있다.

 

• next_permutation: 현재의  수열에서 함수 인자의 범위내의 다음 순열을 구하고 true를 반환한다.
• 다음 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 작다면) false를 반환.

---

std::set 자료구조

std::set은 key값을 갖고있는 고유한 객체를 정렬된 집합을 의미한다.

 

컨테이너

노드 기반 연관 컨테이너

 

큰 특징

• 중복된 키(원소)는 허용하지 않는다.
• std::set 내부적으로 자동 오름차순 정렬이된다.

---

코드

#include <string>
#include <set>
#include <cmath>
#include <algorithm>

using namespace std;

// 소수인지 판단하는 함수
bool CheckFunc(int Number)
{
    // 반복 범위는 2부터 제곱근까지만 해면 된다 2*5나 5*2나 같기때문
    for(int i = 2; i <= sqrt(Number); ++i)
    {
        if(Number % i == 0)
        {
            return false;
        }
    }
    
    return true;
    
    // 유의해야 할 점
    // 판단할때 아래 코드처럼 조건문 내부식을 !=으로하고 return true
    // 반복문 밖에있는 리턴을 false로하면 안된다.
    /*for(int i = 2; i <= sqrt(Number); ++i)
    {
        if(Number % i != 0)
        {
            return true;
        }
    }
    
    return false;*/
}

int solution(string numbers) 
{
    int answer = 0;
    
    // 오름차순 정렬을 해줘야 do while문에서 next_permutation로 판단을 할 수 있음
    // 내림차순 정렬을 하면 next가 아니라 prev로 판단할 수 있다.
    sort(numbers.begin(), numbers.end());
    
    // set을 변수로 둔 이유는 중복된 소수를 판단하기 위해서이다.
    // set의 특징은 자동 정렬 + 중복된 키를 허용하지 않는것
    set<int> setSave;
    
    do
    {
        for(size_t i = 1; i < numbers.size() + 1; ++i)
        {
            // 0번 인덱스부터 i번째까지 판단하여 숫자를 얻어온다
            // 즉 i가 1이라면 ex 1번 기준 1을 얻어오고 i가 2면 17을 얻어온다
            int Numb = stoi(numbers.substr(0, i));
            
            // 1이랑 0은 소수에 포함하면 안되므로 continue
            if(Numb == 1 || Numb == 0)
                continue;
                
            // 소수인지 판단
            if(CheckFunc(Numb))
            {
                // set자료구조에 저장
                setSave.insert(Numb);
            }
        }// 순열함수 이용
    }while(next_permutation(numbers.begin(), numbers.end()));
    
    // 저장된 소수의 데이터 개수를 리턴
    return setSave.size();
}

---

이번 문제를 풀면서 순열관련된 내용을 어떻게 풀이해야할까 찾아보다가 .next_permutation이란 함수를 알게되었다

덕분에 좋은 함수를 알게 되었고 위의 코드에서 set자료구조를 사용했는데 unordered_set.을 사용하는게 더 좋았을 거 같다.

set자료구조의 경우 자동정렬되어 오히려 시간을 더 잡아먹었을 거 같다는 생각이 든다.

(저장하는 값들이 많지 않기때문에 그대로 set으로 코드 올립니다)