Programmers / k진수에서 소수 개수 구하기 / C++

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: k진수에서 소수 개수 구하기 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

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

// visit[0] = 0P0
// visit[1] = P0
// visit[2] = 0P
// visit[3] = P
bool visit[4] = { false };

bool isPrime(long long n) {
	if (n < 2) return false;
	for (int i = 2; i <= sqrt(n); i++)
		if (n % i == 0) return false;
	return true;
}

int solution(int n, int k) {
	int answer = 0;
	string strl = "";
	string str = "";

	while (n > 0) {
		int na = n % k;
		strl += to_string(na);
		n /= k;
	}

	reverse(strl.begin(), strl.end());

	for (char c : strl) {
		if (c == '0') {
			if (!str.empty() && isPrime(stoll(str))) {
				answer++;
			}
			str.clear();
		}
		else str += c;
	}

	if (!str.empty() && isPrime(stoll(str)))
		answer++;

	return answer;
}

 

처음에는 bool visit[4]만들어서 조건을 만족하는 케이스를 구분하려고 했다.

하지만 한 번씩 만족해야할 조건이 없다는 것을 알고 그냥 바로 '0'을 만났을 때 str이 소수인지 확인하고 마지막 str 문자열이 소수인지 체크만 하면 되는 쉬운 문제다.

---

※ 알아야 할 것

 

소수 알고리즘 구하기

소수(Prime Number) 구하기 알고리즘

 

소수를 구하는 알고리즘을 정리해둔 글이다.

 

그리고 10진수의 숫자를 k진수로 바꾸는 방법은 10진수를 k진수로 나눈 나머지를 strl에 추가하고 10진수를 k진수로 나눈다. 그리고 마지막에 reverse를 하면 k진수가 나온다.

이건 직접 손으로 10진수를 2진수로 바꿔보면 바로 감이 올 것이다.