728x90
반응형
문제 : 소수 찾기
풀이 방법
조합과 순열을 적절히 섞어야하며 자릿수도 신경 써야하므로 for문 안에 do while (next_permutation)을 넣었다.
프로그래머스 소수 찾기 11번 케이스만 오답이 나서 뭔가 했는데 numbers를 sort하지 않아서 오류가 났던 것이다.
경우의 수를 전부 체크하고 나면 01과 1은 같은 숫자로 치므로 0도 제거 한 다음, 중복되는 숫자를 제거해서 소수를 체크하면 끝이다
소스 코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool isPrime(int& i)
{
for(int u = 2; u <= i; u++) {
if(i % u == 0 && i == u) {
return true;
}
else if(i % u == 0 && i != u){
return false;
}
}
}
int solution(string numbers) {
int answer = 0;
vector<string> vecNumbers;
// numbers를 오름차순으로 정렬 next_permutation은 정렬되어 있어야함
sort(numbers.begin(), numbers.end());
// 자릿수 별로 조합
for(int i=1; i<=numbers.length(); i++) {
do {
string tmp = "";
for(int u=0; u<i; u++) {
tmp.push_back(numbers[u]);
}
// 011의 0은 필요없으니 맨 앞의 0 제거
while(tmp.front() == '0') tmp.erase(tmp.begin());
if(!tmp.empty()) vecNumbers.push_back(tmp);
} while (next_permutation(numbers.begin(), numbers.end()));
}
// 중복되는 숫자 제거
sort(vecNumbers.begin(), vecNumbers.end());
vecNumbers.erase(unique(vecNumbers.begin(), vecNumbers.end()), vecNumbers.end());
// 소수 개수 체크
for(string s : vecNumbers) {
int i = stoi(s);
if(isPrime(i) == true) answer++;
}
return answer;
}
728x90
반응형
'코딩 테스트 > 프로그래머스' 카테고리의 다른 글
프로그래머스 PCCE 모의고사 1회 문제 코드 정답 풀이 (0) | 2022.09.17 |
---|---|
[프로그래머스 Level 1, C] 수박수박수박수박수박수? (0) | 2022.08.10 |
[프로그래머스 Level 1, Java] 평균 구하기 (0) | 2022.08.04 |
[프로그래머스 Level 1, Java] 정수 제곱근 판별 (0) | 2022.08.04 |
[프로그래머스 Level 2, C++] 최댓값과 최솟값 (0) | 2022.08.03 |