문제 풀이
문제 보고 할 일 정리
1. 소수인지 판단하는 함수 만들기
2. 완전탐색하는 로직 만들기
3. 중복 제거하는 로직 만들기
1, 3은 간단했으나 완전탐색 되도록하는 로직 만드는게 까다로웠다.
1. 소수인지 판단하는 함수 만들기
간단하다.. 더 작은 숫자로 다 나눠서 떨어지는게 하나라도 있으면 false 리턴하면 됨
bool isPrime(int number)
{
if (number < 2)
return false;
for (int div = 2; div < number / div + 1; ++div)
if (number % div == 0)
return false;
return true;
}
2. 완전탐색하는 로직 만들기
완전탐색 문제를 풀 때 나는 보통 재귀로 푸는 편이어서, 이번에도 재귀로 생각을 해봤다.
재귀로 문제를 풀 때 중요한 것은 '이번' 시행과 '다음' 시행의 연관성을 생각해서 1. 각 시행에 필요한 것 (함수 인자) 2. 각 시행의 동작 3. 완료 조건, 동작 을 정하는 것이다.
3. 일단 종료 조건에서는 당연히 만들어진 숫자를 배열에 넣어야 할 것이다.
2. 각 시행에서는 해당 자릿수에 들어갈 숫자를 남은 숫자만큼의 경우의 수로 넣어준다
1. 그러려면 각 시행에는 남은 자릿수, 해당 시점까지 만들어진 숫자, 남은 숫자(종이 조각의), 그리고 종료조건에서 숫자를 저장할 배열의 주소일 것이다.
void recursive(int remainingDigits, int number, vector<int> numbers, vector<int> &primeNumbers)
{
if (remainingDigits == 0)
{
if (isPrime(number))
primeNumbers.push_back(number);
return;
}
for (int i = 0; i < numbers.size(); i++)
{
vector<int> temp(numbers);
temp.erase(temp.begin() + i);
recursive(remainingDigits - 1, number * 10 + numbers[i], temp, primeNumbers);
}
}
3. 중복 제거하는 로직 만들기
sort, unique, erase를 활용하는 방법을 서치해서 찾았다.
sort(primeNumbers.begin(), primeNumbers.end());
primeNumbers.erase(unique(primeNumbers.begin(), primeNumbers.end()), primeNumbers.end());
정답 코드
bool isPrime(int number)
{
if (number < 2)
return false;
for (int div = 2; div < number / div + 1; ++div)
if (number % div == 0)
return false;
return true;
}
void recursive(int remainingDigits, int number, vector<int> numbers, vector<int> &primeNumbers)
{
if (remainingDigits == 0)
{
if (isPrime(number))
primeNumbers.push_back(number);
return;
}
for (int i = 0; i < numbers.size(); i++)
{
vector<int> temp(numbers);
temp.erase(temp.begin() + i);
recursive(remainingDigits - 1, number * 10 + numbers[i], temp, primeNumbers);
}
}
int solution(string numbers)
{
vector<int> primeNumbers;
vector<int> numbersToVector;
for (int i = 0; i < numbers.size(); ++i)
numbersToVector.push_back(numbers[i] - '0');
for (int digits = numbers.size(); digits > 0; digits--)
recursive(digits, 0, numbersToVector, primeNumbers);
sort(primeNumbers.begin(), primeNumbers.end());
primeNumbers.erase(unique(primeNumbers.begin(), primeNumbers.end()), primeNumbers.end());
return primeNumbers.size();
}
결과
다른 사람의 코드
딱히 참고할 만한게 없어서 안가져왔음
'알고리즘 문제 > 프로그래머스' 카테고리의 다른 글
프로그래머스 탐욕법 구명보트 c++ 풀이 (1) | 2021.04.04 |
---|---|
프로그래머스 해시 위장 c++ 풀이 (0) | 2021.04.04 |
프로그래머스 스택/큐 프린터 c++ 풀이 (0) | 2021.03.07 |
프로그래머스 스택/큐 다리를 지나는 트럭 (0) | 2021.02.28 |
프로그래머스 정렬 H-Index c++ 풀이 (0) | 2021.02.28 |