문제 :
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한 사항 :
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예 :
numbers | return |
"17" | 3 |
"011" | 2 |
코드 :
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
bool visited[8]={0,};
string str="",paper;
vector<int> nums;
bool isPrime(int n) {
if (n == 0 || n == 1)return false;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0)return false;
}
return true;
}
void dfs(int num, int size) {
if (num == size) {
return;
}
for (int i = 0; i < size; i++) {
if (!visited[i]) {
visited[i] = true;
str.push_back(paper[i]);
nums.push_back(stoi(str));
dfs(num+1, size);
visited[i] = false;
str.pop_back();
}
}
}
int solution(string numbers) {
int answer = 0;
paper=numbers;
dfs(0,paper.size());
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
for (int j = 0; j < nums.size(); j++) {
if (isPrime(nums[j])) answer++;
}
return answer;
}
다시 한번 짚고 넘어가기 :
-테스트 케이스 2,10,11번이 실패한 이유
소수인지 판별하는 isPrime함수에서 for문의 범위인 sqrt(n)을 포함 시키지 않았다.
-소수 판별할때 범위를 2~sqrt(n)으로 하여 빠르게 검색한다.
-조합문제일 경우에는 dfs를 사용하여 중복된 숫자를 고르지 않을 경우에는 bool visited 변수를 사용한다.
'Algorithm > 프로그래머스' 카테고리의 다른 글
[프로그래머스/level2/c++] [2020 KAKAO BLIND RECRUITMENT] 문자열 압축 (0) | 2021.02.03 |
---|---|
[프로그래머스/level2/c++] 124나라의 숫자 (0) | 2021.02.02 |
[프로그래머스/level2/c++] 더 맵게 (0) | 2021.01.25 |
[프로그래머스/level2/c++] 가장 큰 수 (0) | 2021.01.24 |
[프로그래머스/level2/c++] 가장 큰 정사각형 찾기 (0) | 2021.01.24 |