[ 프로그래머스 K진수에서 소수 개수 구하기(Lv2) ] (C++)

프로그래머스의 K진수에서 소수 개수 구하기(Lv2) 문제이다.

 

[ 문제풀이 ]

주어진 숫자 n을 k진수로 바꿨을 때, 조건에 맞는 소수가 몇 개 인지 구해야 하는 문제이다.

순차대로 문제를 해결해보자.

 

#1. K진수로의 변환

가장 먼저 우리는 주어진 숫자 n을 k진수로 변환시켜 주어야 한다.

본인은 10진수를 2진수로 바꿀 때, 2로 나눈 나머지를 계속해서 저장해가는 방식과 똑같이 n을 k로 나눈 나머지를 계속해서 저장하는 방식으로 구현하였다. 그리고 본인은 이 값을 'string'형태의 데이터로 저장을 해주었다.

왜냐하면, k로 나눈 나머지를 순차적으로 저장을 하게 되면, 결국 이를 뒤집어 줘야 하기도 하고, 우리는 각각의 숫자를 찾아가면서 조건에 맞는 소수를 찾아야 하기 때문에 문자열이 더 편하다고 생각을 했기 때문이다.

위에서 뒤집어 줘야 한다는 것은 예시로 나타내면 다음과 같다.

6을 2진수로 바꿀 때, 6 % 2 = 0 → 3 % 2 = 1 → 1 % 2 = 1 을 순차적으로 저장하게 되면 '011' 이라는 값이 나오게 되는데, 사실 6을 2진수로 바꾸게 되면 011이 아닌 110이 나와야 하기 때문이다. 그래서 이렇게 뒤집는 과정이 필요하다.

이 과정을 소스코드로 나타내면 다음과 같다.

string num;
void changeNum(int n, int k) {
	while (n > 0) {
		num += to_string(n % k);
		n /= k;
	}
	reverse(num.begin(), num.end());
}

위의 코드에서 'num' 이라는 변수가 주어진 숫자 n을 k진수로 변환했을 때, 그 값을 string형태로 저장하기 위해 선언해 놓은 변수이다. 그리고 마지막에 reverse 함수를 통해서 주어진 문자열을 거꾸로 뒤집어 주었다.

 

#2.  소수 찾기

이제 k진수로 변환되어 있는 값을 가지고 있으니, 이를 통해서 조건에 만족하는 소수를 찾아보자.

조건에 만족하는 소수가 여러가지가 있는데 이를 통합해서 쉽게 한 마디로 정리해보면 "0을 기준으로 숫자를 짤랐을 때, 그 숫자가 소수인지 아닌지" 만 판단을 해주면 된다.

몇 가지 예시를 통해서 위의 말을 생각해보자.

1. "0 A B C D E"

2. "A 0 B C D 0 E"

3. "A B C D E 0 "

4. "A B C D E"
(편의 상, 실제 숫자가 아닌 숫자를 A, B, C, D, E로 표현하였습니다. 위의 예시에서 A B C D E 는 숫자라고 생각하시면 됩니다.)

먼저, 첫 번째 예시에 있는 숫자를 0을 기준으로 잘라보자.

그렇게 되면, 'A B C D E' 라는 숫자가 나오게 된다. 즉, 이 경우에는 문제에서 나와있는 '0P'의 형태가 되는 것이다.

왼쪽에만 '0'이 있고, 오른쪽에는 더 이상 '0'이 존재하지 않는 꼴이다.

두 번째 예시를 0을 기준으로 잘라보면, 'A' , 'B C D' , 'E' 가 나오게 된다.

'A'는 'P0'의 형태를, 'B C D'는 '0P0'의 형태를, 'E'는 '0P'의 형태가 된다.

나머지 3, 4번 예시도 마찬가지이다.

즉, 문제에서 언급한 소수가 여러가지가 있는데 이를 통합해서 한 마디로 정리해보면 "0을 기준으로 숫자를 짜르고, 그 숫자가 소수인지 판단하여라" 라고 생각할 수 있다.

그래서 본인은 #1에서 문자열의 형태로 저장한 데이터에서 하나하나 탐색을 하면서 '0'이 아닐 때에는, 숫자를 저장해주고 '0'일 때에는 지금까지 저장한 숫자들이 소수인지 판단해 주었다.

주의해야 할 점이, 모든 문자열에 대한 탐색이 끝난 후, 마지막에 탐색을 한번 더 해줘야 하는 경우가 발생할 수도 있다는 것이다.

위의 예시에서 1번 예시를 한번 보자.

'0'일 때에는 그냥 넘어가고, 그 이후에 숫자들을 저장하게 되면 'A B C D E'가 나오게 된다.

이 경우에는 문자열 탐색이 끝나서 이대로 종료될 수가 있는데, 이렇게 종료시키지 말고 마지막으로 한번 더 체크를 해줘야 한다.

왜냐하면, 'A B C D E'라는 숫자가 남아있기 때문이다.

이를 코드로 나타내면 다음과 같다.

int findAnswer() {
	int answer = 0;
	string str = "";
	for (auto c : num) {
		if (c == '0') {
			if (str.length() == 0) continue;
			if (checkPrime(stol(str)) == true) {
				answer++;
			}
			str = "";
		}  else {
			str += c;
		}
	}

	if (str.length() != 0) {
		if (checkPrime(stol(str)) == true) answer++;
	}
	return answer;
}

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
string num;
 
void changeNum(int n, int k) {
    while (n > 0) {
        num += to_string(n % k);
        n /= k;
    }
    reverse(num.begin(), num.end());
}
 
bool checkPrime(long long n) {
    if (n == 0 || n == 1) {
        return false;
    }
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}
 
int findAnswer() {
    int answer = 0;
    string str = "";
    for (auto c : num) {
        if (c == '0') {
            if (str.length() == 0) continue;
            if (checkPrime(stol(str)) == true) {
                answer++;
            }
            str = "";
        }  else {
            str += c;
        }
    }
 
    if (str.length() != 0) {
        if (checkPrime(stol(str)) == true) answer++;
    }
    return answer;
}
 
int solution(int n, int k) {
    int answer = -1;
    changeNum(n, k);
    answer = findAnswer();
    return answer;
}