[Programmers] 소수 찾기 (+unique, erase)

📍 [C++] vector 중복 원소 제거하는 법

#include <algorithm> 헤더 필수! 정렬 필수!

sort(vector.begin(), vector.end());
vector.erase(unique(vector.begin(), vector.end()), vector.end());

• unique 함수
  중복되지 않는 원소를 앞에서부터 채워나간다.(중복되는 원소는 뒤에 채워진다.)
  중복되지 않는 원소로 채워나간 부분의 end()를 반환한다.
  ex) 1, 2, 4, 4, 5 => 1, 2, 4, 5, 4

• erase 함수
  vector에서 특정 원소를 삭제한다.
  파라미터가가 1개인 경우는 해당 위치의 원소를 삭제하고, 2개인 경우는 해당 범위의 원소를 삭제한다.
  
  
  

문제 설명

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

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

제한 사항

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

소스코드

C++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// 오름차순 정렬을 위한 함수
bool cmp(char a, char b) {
    return a > b;
}

int solution(string numbers) {
    int answer = 0;
    sort(numbers.begin(), numbers.end(), cmp);
    int max = stoi(numbers);
    
    /**
     에라토스테네스의 체를 이용해 소수를 구함.
    **/
    bool chk[10000000] = {0, };
    chk[0] = chk[1] = 1; // 소수가 아닌 0, 1은 제외
    // 조각을 붙여 만들 수 있는 최대값까지의 수에 대해 소수 판별
    for(int i=2;i<=max;i++) {
        if(!chk[i]) {
            for(int j=i+i;j<=max;j+=i) {
                chk[j] = true;
            }
        }
    }
    
    vector<char> v;    
    vector<int> num;
    // 종이 조각 각각을 분리 
    for(int i=0;i<numbers.size();i++) {
        v.push_back(numbers[i]);
    }
    sort(v.begin(), v.end());

    // 순열을 통해 모든 숫자 만듦
    do {
        string tmp = "";
        for(int i=0;i<v.size();i++) {
            tmp.push_back(v[i]);
            num.push_back(stoi(tmp));
        }
    } while (next_permutation(v.begin(), v.end()));
    
    sort(num.begin(), num.end());
    num.erase(unique(num.begin(), num.end()), num.end()); // 중복 숫자 제거
    
    // 소수의 갯수 체크
    for(int i=0;i<num.size();i++) {
        if(!chk[num[i]]) {
            answer++;
        }
    }
    
    return answer;
}

Java

import java.util.*;
class Solution {
    public static Set<Integer> set = new HashSet<>();
    public int solution(String numbers) {
        int answer = 0;
        String[] num = numbers.split("");
        boolean visited[] = new boolean[numbers.length()];
        dfs(num, visited, ""); // 가능한 모든 수 만들기
        
        // 소수인지 체크
        for(Integer s : set) {
            if(s < 2) continue;
            boolean check = true;
            for(int i = 2; i*i <= s; i++) {
                if(s%i == 0) {
                    check = false;
                    break;
                }
            }
            if(check) answer += 1;
        }
        
        return answer;
    }
    
    public void dfs(String[] num, boolean[] visited, String str) {
        for(int i = 0; i < num.length; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            set.add(Integer.parseInt(str+num[i]));
            dfs(num, visited, str+num[i]);
            visited[i] = false;
        }
    }
}

소감

에라토스테네스의 체를 이용해 소수 구하는 방법, 순열
잊지말자!!
특히, 순열 오랜만에 봐서 더 생각 안나고 헷갈렸다ㅠㅠ
다시 한 번 풀어봐야 할 문제 👩‍💻💡