프로그래머스 92335 - k진수에서 소수 개수 구하기 (Lv.5)

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

// 프로그래머스 92335 - k진수에서 소수 개수 구하기 (Lv.5)
// https://school.programmers.co.kr/learn/courses/30/lessons/92335

// 문제 설명
// 양의 정수 n을 k진수로 바꿨을 때, 조건에 맞는 소수(P)의 개수를 반환하라.
// 조건은 0P0 / P0 / 0P / P 형태 — 즉 P 안에 0이 없고, 앞뒤가 0이거나 문자열 경계다.
// P는 k진수 표기를 그대로 10진수 수로 읽은 값으로 소수 판정한다.

// 제약 조건
// 1 <= n <= 1,000,000
// 3 <= k <= 10

// Example
// Input : n = 437674, k = 3
// Output: 3    (211020101011 → 211, 2, 1, 1, 11 → 소수는 211, 2, 11)
//
// Input : n = 110011, k = 10
// Output: 2    (110011 → 11, 11 → 둘 다 소수)

// 접근 — 진법 변환 + 0을 구분자로 토큰 분리 + 제곱근 소수 판정
// "앞뒤가 0 또는 경계"라는 조건은 결국 0을 구분자로 문자열을 자르는 것과 같다.
// 정규식이나 4가지 형태 분기 없이, 0에서 끊고 끊긴 조각만 소수 판정하면 된다.
// 1) n을 k진수 문자열로 변환 (나머지를 모아 뒤집는다).
// 2) 왼쪽부터 한 자리씩 cur = cur * 10 + digit 으로 누적하고, 0이나 끝을 만나면 토큰 확정.
// 3) 토큰을 sqrt까지만 나눠 소수 판정.
// 자리 수는 k = 3일 때 최대 13자리(3^12 <= 10^6 < 3^13)이므로 토큰 값이 최대 약 1.1 x 10^12.
// int로 받으면 오버플로 — cur은 long long이어야 한다.
// 시간 O(log_k n * sqrt(최대 토큰)), 공간 O(log_k n)

#include <string>
#include <algorithm>

using namespace std;

// n을 k진수 문자열로 변환
string toBase(int n, int k) {
    string s;
    while (n > 0) { s += char('0' + n % k); n /= k; }
    reverse(s.begin(), s.end());               // 나머지는 낮은 자리부터 나오므로 뒤집는다
    return s;
}

bool isPrime(long long v) {
    if (v < 2) return false;                   // 1은 소수가 아니다 — 토큰 "1"이 자주 나온다
    for (long long d = 2; d * d <= v; d++)     // sqrt까지만 확인
        if (v % d == 0) return false;
    return true;
}

int solution(int n, int k) {
    string s = toBase(n, k);
    int answer = 0;
    long long cur = 0;                         // 진행 중인 토큰의 10진수 값

    // i == s.size() 를 마지막 구분자처럼 취급 — 끝에 0을 붙이는 특수 처리가 사라진다
    for (int i = 0; i <= (int)s.size(); i++) {
        if (i == (int)s.size() || s[i] == '0') {
            if (cur > 0 && isPrime(cur)) answer++;
            cur = 0;                           // 연속된 0은 cur == 0 이라 그냥 건너뛴다
        } else {
            cur = cur * 10 + (s[i] - '0');
        }
    }
    return answer;
}

정리

• 문제가 준 0P0 / P0 / 0P / P 네 가지 형태는 패턴 매칭이 아니라 “0으로 자르기” 한 문장으로 접힌다. 네 형태를 그대로 조건문으로 옮기면 경계(문자열 시작·끝)에서 인덱스 처리가 갈라지는데, “0을 구분자로 보고 토큰을 모은다”로 바꾸면 형태 구분 자체가 사라진다. 문제 설명의 표현을 그대로 코드로 번역하지 말고 같은 뜻의 더 단순한 표현을 먼저 찾는다.
• 루프를 i <= s.size()로 한 칸 더 돌린 게 두 번째 단순화다. 마지막 토큰만 루프 밖에서 따로 확정하는 코드는 같은 판정 로직이 두 곳에 복제되는데, 문자열 끝을 가상의 구분자로 취급하면 확정 로직이 한 군데로 모인다. 연속된 0도 cur == 0으로 자연히 걸러진다.
• 오버플로가 이 문제의 실제 함정이다. n <= 10^6만 보고 int로 받으면 틀린다. k = 3이 최악으로, 3^12 = 531,441 <= 10^6 < 3^13이라 최대 13자리가 나온다. 실제로 n = 797,161은 3진수로 1111111111111이고 토큰을 10진수로 읽으면 약 1.1 x 10^12 — int 상한(약 2.1 x 10^9)의 500배다. 제약이 작아 보여도 변환 후 값의 상한을 따로 계산하는 습관이 필요하다(위장 42578에서 곱의 누적 상한을 먼저 잡은 것과 같은 점검).
• 소수 판정은 d * d <= v로 제곱근까지만 본다. 토큰 상한 1.1 x 10^12의 제곱근은 약 1.05 x 10^6이고 토큰 개수는 많아도 7개 수준이라 전체 연산이 10^7 안쪽 — Lv.5 효율성 기준에서 여유가 있다. 여기서 d <= v / 2 같은 절반 순회로 쓰면 10^12 스케일이 되어 그대로 시간 초과다. 반대로 에라토스테네스 체는 상한이 10^12여서 메모리가 감당되지 않으므로, 후보가 몇 개뿐일 때는 체가 아니라 개별 시행 나눗셈이 맞다.
• isPrime의 v < 2 가드가 정답을 가른다. 3진수 표기에는 토큰 1이 흔하게 등장하고(예제 1에도 두 개), 1을 소수로 세면 3이 아니라 5가 나온다. 1은 소수가 아니다를 판정 함수 첫 줄에 박아두면 호출부에서 매번 신경 쓸 일이 없다.
• 검증: 예제 2개(3, 2)와 경계 케이스(n = 1 → 0, n = 2 → 1), 13자리 오버플로 케이스(n = 797,161) 통과 (MSVC /std:c++17 컴파일·실행). 커리큘럼 95번.

핵심 요약 — 0P0·P0·0P·P 네 형태는 “0을 구분자로 토큰 자르기” 한 줄로 접히고, 문자열 끝을 가상의 구분자로 취급하면 마지막 토큰 특수 처리도 사라진다. 진짜 함정은 n <= 10^6이 아니라 변환 후 토큰 값 — k = 3에서 13자리(약 1.1 x 10^12)까지 커지므로 int가 아니라 long long이어야 한다.