lv2 / K진수에서 소수 개수 구하기 / 카카오 / C++

https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

---

비록 N이 100만까지밖에 안되지만, 이를 K진수로 변환하면 더 커질수 있기 때문에, K진수로 변환한 값은 문자열로 받아서 처리하는게 안전하다고 판단했다. 이후, 0을 기준으로 숫자를 쪼개고, 각각 소수판별을 해주면 된다. 만약 테스트 케이스를 통과하지 못했다면, 필자의 글이 도움이 되길 바라며 필자가 겪은 오류와 오답을 적어보도록 하겠다.

 

1. 테스트케이스 1번은 극한 케이스이다. (맨 뒤에 나오는 사진 보면 알겠지만) 다른 케이스에 비해 시간과 메모리 모두 많이 사용한다. 이는 매우 큰 숫자가 들어온다는 뜻이다. 만약 에라토스테네스의 체를 이 문제에 적용했다면, 추천하지 않는다. 10진수로만 했으면 100만까지만 따지면 되겠지만, 이 문제에서는 K진수로 변환하기 때문에, 어디까지 판단해야할지 감을 잡기 힘들다. 일반적인 소수 판별법을 사용하도록 한다. 만약 일반적인 소수판별법을 사용했는데도 틀렸다면, 판별 범위때문일 것이다. n이 소수인지 판단하기 위해 보통 2 ~ n까지 나누는 작업을 진행할텐데, 사실 2 ~ sqrt(n)까지만 나눠봐도 충분하다. N = a*b이고 a < b라고 하면, a는 1 ~ sqrt(n)까지 만족할 것이고, 이 범위를 넘어서면 a와 b가 대칭되기 때문.
2. 숫자의 크기를 잘 생각하자. 앞서 말했듯, 100만에 근접한 큰 수를 K진수로 변환하면 숫자가 정말 커질 것이다. 만약 거기에 0이 정말 적게 들어있다면, 판별해야하는 숫자 역시 매우 커질 것. int보다 더 큰 자료형을 사용하도록 하자.
3. 문자열 0을 조심하자. C++에 경우 (필자의 지식한정) string에 split기능이 없기 때문에 직접 split해야한다 . 만약 n = 39에 k = 3이라면, 1110으로 변환될 것이고, 맨 마지막 0을 제대로 처리해야한다. 또한, n = 28에 k = 3이라면, 1001로 변환되는데, 중간의 0에서 만약 저장된 숫자가 없는 상태에서 저장하려고 했다면, 예외처리를 해줘야 할 것이다. 만약 이것이 제대로 되어있지 않다면 테스트케이스 12번에서 오류가 날 가능성이 높다. (다른 하나도 오류가 날 가능성이 높은데, 11번인지 13번인지 헷갈린다.) (22.09.08) stringstream 헤더를 통해 문자열 split을 용이하게 할 수 있다. 단, 이때 delim을 통해 얻어온 token이 빈칸인 경우를 조심해야한다.

 

#include <bits/stdc++.h>
using namespace std;
using ull = uint64_t;

void dec_to_kbase(string& result, int dec, int k) {
    if (k == 0) result = to_string(dec);

    while (dec) {
        result += to_string(dec % k);
        dec /= k;
    }
    reverse(result.begin(), result.end());
}

bool is_prime(ull n) {
    if (n <= 1) return false;

    for(ull i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int solution(int n, int k) {
    int answer = 0;
    string nBase;
    dec_to_kbase(nBase, n, k);
    vector<ull> target;
    string p;
    
    for(char x : nBase) {
        if (x == '0') {
            if (p != "") {
                target.push_back(stoull(p));
                p = "";
            }   
        }
        else p += x;
    }
    if (p != "") target.push_back(stoull(p));
    for (ull x : target) {
        if (is_prime(x)) answer++;
    }
    return answer;
}

 

---

(22.09.08) 생각해보니까 이 전까지 문자열 split을 잘만 했는데 왜 이 문제를 풀때는 까먹은건지 모르겠다.

 

#include <bits/stdc++.h>
using namespace std;
using ull = uint64_t;

void dec_to_kbase(string& result, int dec, int k) {
    if (k == 0) result = to_string(dec);

    while (dec) {
        result += to_string(dec % k);
        dec /= k;
    }
    reverse(result.begin(), result.end());
}

bool is_prime(ull n) {
    if (n <= 1) return false;

    for(ull i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int solution(int n, int k) {
    int answer = 0;
    string nBase;
    dec_to_kbase(nBase, n, k);
    vector<ull> target;
    string p, token;
    
    stringstream sstream(nBase);
    while(getline(sstream, token, '0')) 
        if (token != "") target.push_back(stoull(token));

    for (ull x : target) {
        if (is_prime(x)) answer++;
    }
    return answer;
}