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

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

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

1. 서론

 

푼 지가 오래돼서 기억이 잘 안 나는데... 꽤나 애먹었던 기억나는 문제. 완전 탐색 카테고리에 있길래 공부해 보려고 풀었다.

 

2. 문제 풀이

 

숫자가 문자열로 주어진다. 이를 각 자리 숫자 조합을 활용해서 숫자를 새로 만드는데 만들 수 있는 숫자의 경우의 수 중에서 소수는 몇 개를 만들 수 있는가를 반환하는 문제다.

 

숫자의 순서가 의미가 있기 때문에 순열문제이다. 입력받은 문자열을 분리해서 숫자 배열에 넣어주고 순열 코드를 돌려서 값을 구한 다음 중복되는 값들을 제외해주고 구한 값들 중에서 소수인 값을 구하는 식으로 풀었다.

 

3. 코드 설명

 

순열을 재귀로 구현한 버전)

 

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

using namespace std;

vector<int> v;

void swap(char &a, char &b)
{
    char tmp = a;
    a = b;
    b = tmp;
}

void perm(string num, int d, int n, int r)
{
    if (d == r)
    {
        string s = "";
        for (int i = 0; i < r; i++)
            s += num[i];
        v.push_back(stoi(s));
        return;
    }
    
    for (int i = d; i < n; i++)
    {
        swap(num[d], num[i]);
        perm(num, d + 1, n, r);
        swap(num[d], num[i]);
    }
}

int solution(string numbers) {
    
    for (int i = 1; i <= numbers.size(); i++)
        perm(numbers, 0, numbers.size(), i);
    
    sort(v.begin(), v.end());
    
    vector<int> t;
    t.push_back(v[0]);
    for (int i = 1; i < v.size(); i++)
        if (t.back() != v[i])
            t.push_back(v[i]);
    
    int answer = 0;
    for (int i = 0; i < t.size(); i++)
    {
        int cnt = 0;
        for (int j = 2; j <= t[i]; j++)
            if (t[i] % j == 0)
                cnt++;
        
        if (cnt == 1)
            answer++;
    }
    
    return answer;
}

 

next_permutation 함수를 사용해 순열을 구현한 버전)

 

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

using namespace std;

int solution(string numbers) {
    
    vector<int> v;
    
    sort(numbers.begin(), numbers.end());
    for (int i = 1; i <= numbers.size(); i++)
    {
        int n = numbers.size(), r = i;
        do {
            string s = "";
            for (int j = 0; j < r; j++)
                s += numbers[j];
            v.push_back(stoi(s));
        } while(next_permutation(numbers.begin(), numbers.end()));
    }

    sort(v.begin(), v.end());
    
    vector<int> t;
    t.push_back(v[0]);
    for (int i = 1; i < v.size(); i++)
        if (t.back() != v[i])
            t.push_back(v[i]);
    
    int answer = 0;
    for (int i = 0; i < t.size(); i++)
    {
        int cnt = 0;
        for (int j = 2; j <= t[i]; j++)
            if (t[i] % j == 0)
                cnt++;
        
        if (cnt == 1)
            answer++;
    }
    
    return answer;
}

 

답을 구할 때 계산이 빠를 것 같아서 정렬을 한 번 돌리고 시작했다. 근데 정렬과 답 구하는 거에 별로 상관관계가 없을 것 같아서 정렬 부분 빼고 돌렸더니 11번 테케가 틀렸다... 11번 테케 틀리는 사람은 정렬을 해보세요(원래 next_permutation 돌릴 때는 정렬을 돌려야 하는 걸로 추정, 왜냐면 재귀로 구현했을 때는 정렬 안 했는데 됐음)

 

어쨌든 그러고나서 순열로 구한 값들을 정렬하고 중복된 값을 제외하고 소수를 cnt변수에 저장해 구해줌.

 

은근히 쉬운 듯 어려운듯한 문제 일부 테케 때문인지 질문하기도 엄청 많더라는....