[프로그래머스] k진수에서 소수 개수 구하기 풀이 (2022 카카오 코딩테스트)

| |
프로그래머스 - k진수에서 소수 개수 구하기 C++ 풀이 (2022 카카오 블라인드 채용 1차 코딩테스트)


문제 설명

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

  • 0P0처럼 소수 양쪽에 0이 있는 경우
  • P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
  • 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
  • P처럼 소수 양쪽에 아무것도 없는 경우
  • 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
    • 예를 들어, 101은 P가 될 수 없습니다.

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.


제한사항

  • 1 ≤ n ≤ 1,000,000
  • 3 ≤ k ≤ 10


풀이

문제 난이도 자체는 분명 높다고는 할 수 없다. 다만 낮은 난이도 유형의 여러 문제를 합쳐놓은 꼴이다. 그래서 이 문제를 실전에서 풀어내려면 다양한 문제를 접해봤어야 한다. 문제에서 요구하는 사항은 다음과 같다.

  • 진수 변환
  • 문자열과 구현
  • 소수 판정
  • 큰 수

진수 변환과 같은 경우 본 문제에서는 k가 10을 넘어가지 않으므로 알파벳까지 등장할 일은 없으므로 쉽게 구현할 수 있다. 특히 진수 변환과 같은 경우 재귀를 사용하면 간결하게 구현이 가능하다. 자세한 것은 아래 전체 코드 참조.

문제에서 제시된 0과 관련된 여러 조건들을 종합하면 0을 기준으로 자른 숫자들에 대한 소수 판정이다. C++에서는 python과 다르게 split 함수를 지원하지 않기 때문에 직접 구현해야 하는데, stringstream을 사용하면 그나마 간결하게 구현할 수 있다. 자세한 것은 아래 전체 코드 참조.

소수 판정과 같은 경우 관련 알고리즘을 공부한 사람이라면 에라토스테네스의 체를 떠올릴 것이다. 하지만 본 문제에는 이 방법을 쓰면 안된다. 간혹 진수 변환 이후 int 범위를 넘어서는 소수가 등장하기 때문이다. 따라서 에라토스테네스의 체로 구할 수 있는 범위를 넘어서므로 각각의 수마다 long long으로 취급하고 일일이 반복문으로 나누어서 소수임을 판별해야 한다. 필자는 실제 코딩테스트에서도 본 문제에서 같은 이슈로 시간을 많이 허비했었는데, 수개월 후 다시 푸는 지금도 같은 실수를 반복했다… 오히려 에라토스테네스의 체를 모르고 python을 사용하시는 분들은 쉽게 맞추셨을 것 같다.

마지막으로 stoi 또는 stoll 같은 함수들은 인자로 공백이 주어지면 런타임 에러를 발생시킨다. 따라서 split 함수나 main 함수의 반복문 중 최소 한 곳에서는 공백을 걸러내는 작업을 해주어야 한다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <string>
#include <sstream>
#include <vector>
#include <cmath>
using namespace std;

// '0'을 기준으로 문자열 자르기
vector<string> split(string& str) {
    vector<string> ret;
    stringstream ss(str);
    string temp;
    
    while(getline(ss,temp,'0'))
        if(temp!="")
            ret.push_back(temp);
    
    return ret;
}

// long long 주의!
bool isPrime(long long n) {
    if(n == 1) return false;
    for(long long i=2; i<=sqrt(n); i++)
        if(n%i == 0) return false;
    return true;
}

// n을 k진수로 변환
string convert(int n, int k) {
    if(n == 0) return "";
    return convert(n/k,k) + (char)(n%k+'0');
}

int solution(int n, int k) {
    int answer = 0;
    
    string num = convert(n,k);
    vector<string> nums = split(num);
    
    for(string s: nums)
        if(isPrime(stoll(s)))
            answer++;
    
    return answer;
}
0%