728x90
순열을 구현하는 방법에 대해 공부할 수 있었던 문제.
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
문제 풀이
1. 순열 구현
vector<int> all_nums; // 중복되는 숫자를 걸러주는 class
//순열을 구현
string swap(string str, int depth, int i)
{
char tmp = str[depth];
str[depth] = str[i];
str[i] = tmp;
return str;
}
void permutation(string str, int depth, int n, int r)
{
if (depth == r){
all_nums.push_back(stoi(str.substr(0, r)));
return;
}
for(int i = depth; i < n; i++) {
str = swap(str, depth, i);
permutation(str, depth + 1, n, r);
str = swap(str, depth, i);
}
}
bool is_decimal(int num){
for (int i=2; i<=sqrt(num); i++){
if (num%i == 0) return false;
}
if(num<=1) return false;
return true;
}
2. vector 내 중복값 제거
sort(all_nums.begin(), all_nums.end());
all_nums.erase(unique(all_nums.begin(), all_nums.end()), all_nums.end());
3. 소수 여부 판별
bool is_decimal(int num){
for (int i=2; i<=sqrt(num); i++){
if (num%i == 0) return false;
}
if(num<=1) return false;
return true;
}
전체 풀이
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
vector<int> all_nums; // 중복되는 숫자를 걸러주는 class
//순열을 구현
string swap(string str, int depth, int i)
{
char tmp = str[depth];
str[depth] = str[i];
str[i] = tmp;
return str;
}
void permutation(string str, int depth, int n, int r)
{
if (depth == r){
all_nums.push_back(stoi(str.substr(0, r)));
return;
}
for(int i = depth; i < n; i++) {
str = swap(str, depth, i);
permutation(str, depth + 1, n, r);
str = swap(str, depth, i);
}
}
bool is_decimal(int num){
for (int i=2; i<=sqrt(num); i++){
if (num%i == 0) return false;
}
if(num<=1) return false;
return true;
}
int solution(string numbers) {
int answer = 0;
//1. 1 ~ numbers.length 자리의 숫자 조합을 생성한다.
for (int i=1; i<=numbers.length(); i++){
permutation(numbers, 0, numbers.length(), i);
}
//2. vector 중복 숫자 제거
sort(all_nums.begin(), all_nums.end());
all_nums.erase(unique(all_nums.begin(), all_nums.end()), all_nums.end());
//3. 각 숫자가 소수인지 판별
while(all_nums.size()!=0){
int number = all_nums.back();
all_nums.pop_back();
if (is_decimal(number)) answer++;
}
return answer;
}
728x90
'알고리즘' 카테고리의 다른 글
[프로그래머스] 체육복 C++ (0) | 2021.12.04 |
---|---|
[프로그래머스] 카펫 C++ (완전탐색) (0) | 2021.12.04 |
[프로그래머스] 이중우선순위큐 c++ (0) | 2021.12.04 |
[프로그래머스] 디스크 컨트롤러 C++ (heap) (0) | 2021.11.21 |
[프로그래머스] 더 맵게 C++ (0) | 2021.11.21 |