문제 보기 · Level 2 · 2022 KAKAO BLIND RECRUITMENT · 정답률 63% · 푼 사람 20,413명 (2026-09-30 기준)1
문제
양의 정수 n을 k진수로 쓴 문자열에서, 양옆이 0이거나 문자열의 끝인 자리에 놓인 수 덩어리 P를 찾는다. P에는 0이 들어 있지 않다. P를 10진수로 읽었을 때 소수인 것의 개수를 돌려준다.
- 1 ≤ n ≤ 1,000,000
- 3 ≤ k ≤ 10
풀이
막히면 한 단계씩 펼친다.
필요한 개념
- 진법과 자릿수: n을 k진수로 바꾸기
- 리스트와 문자열:
split("0")으로 덩어리 나누기 - 소수와 산술의 기본정리: 소수인지 확인하기
1단계 · 작은 예로 손으로 풀기
n = 77, k = 4
- 77을 4진수로: 77 = 1 × 64 + 0 × 16 + 3 × 4 + 1 → “1031”
- 0을 기준으로 나눈다: “1”, “31”
- 10진수로 읽는다: 1은 소수가 아니고, 31은 소수다
답은 1이다. “양옆이 0이거나 끝”이라는 조건은 “0으로 잘라 나온 덩어리”와 같은 말이다.
2단계 · 가장 단순한 방법과 그 속도
n ≤ 100만을 3진수로 쓰면 최대 13자리다. 덩어리를 10진수로 읽으면 가장 커도 약 2.2조(2,222,222,222,222)다.
소수 판정을 “2부터 P − 1까지 모두 나눠 보기”로 하면 2조 번이라 안 된다. \(\sqrt{P}\)까지만 나눠 보면 약 150만 번이고, 덩어리가 몇 개뿐이라 된다.
3단계 · 핵심 아이디어
- k진수 만들기: n을 k로 나눈 나머지가 끝자리다. 몫으로 바꿔 되풀이하고, 모은 나머지를 거꾸로 붙인다.
- 덩어리:
split("0")으로 자른다. 0이 이어지면 빈 문자열이 생기니 건너뛴다. - 소수 판정: 2 미만이면 소수가 아니다. i = 2, 3, …을 i × i ≤ P인 동안만 나눠 본다. P가 두 수의 곱 a × b(a ≤ b)라면 작은 쪽 a는 \(\sqrt{P}\) 이하라서, 거기까지 나누어떨어지는 수가 없으면 소수다.
4단계 · 코드 흐름
- n을 k진수 문자열로 바꾼다.
- 0으로 잘라 빈 조각을 뺀 덩어리들을 얻는다.
- 덩어리마다 정수로 바꿔 소수인지 보고, 소수면 센다.
- 센 수를 돌려준다.
5단계 · 파이썬 코드
def is_prime(x):
if x < 2:
return False
i = 2
while i * i <= x: # √x까지만
if x % i == 0:
return False
i += 1
return True
def solution(n, k):
digits = ""
while n > 0:
n, r = divmod(n, k) # r이 지금 끝자리
digits = str(r) + digits # 앞에 붙여 거꾸로 모은다
return sum(1 for part in digits.split("0") if part and is_prime(int(part)))
is_prime을solution밖에 따로 만들었다. 답안 파일 안이라면 어디에 둬도 된다.divmod(n, k): (몫, 나머지)다. 나머지가 k진수의 끝자리가 된다.if part and ...: 빈 문자열(0이 이어져 생긴 것)은 건너뛴다.int(part): 덩어리를 10진수로 읽는다. k진수로 읽지 않는다.sum(1 for ... if ...): 조건에 맞는 것의 개수다.
6단계 · 실행 추적
n = 437674, k = 3 → “211020101011”
| 덩어리 | 10진수 값 | 소수? |
|---|---|---|
| 211 | 211 | 예 |
| 2 | 2 | 예 |
| 1 | 1 | 아니오 |
| 1 | 1 | 아니오 |
| 11 | 11 | 예 |
답은 3이다.
7단계 · 복잡도와 흔한 실수
진법 변환은 자릿수만큼, 소수 판정은 덩어리마다 \(O(\sqrt{P})\)다. 가장 큰 덩어리가 약 2조라 판정 한 번에 최대 약 150만 번이다.
- 1을 소수로 센다.
- 덩어리를 k진수로 읽는다(
int(part, k)). 문제는 10진수로 읽으라고 한다. - 빈 조각을
int("")로 바꾸다 오류가 난다. - 소수 판정을 P − 1까지 해서 시간이 초과된다.
검증: 문제의 예시 2개를 통과했고, 무작위 n 2,000개(k = 3~10)에서 “문자열의 모든 구간을 보며 0P0·P0·0P·P 네 모양을 문제 문장 그대로 찾는” 느린 풀이와 결과가 같았다. 소수 판정은 에라토스테네스의 체와 10만 이하에서 일치했다 — 03_pg92335_p1.py
-
프로그래머스 스쿨, “k진수에서 소수 개수 구하기” (https://school.programmers.co.kr/learn/courses/30/lessons/92335), 2026-09-30 조회. ↩