[2022 KAKAO Blind Recruitment] Q2. k진수에서 소수 개수 구하기 (C++, Python, Java)

문제 링크

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

 

예상 난이도

S2

 

알고리즘 분류

수학

 

풀이

사실 문제를 처음 풀 당시에 설명이 조금 헷갈린다는 느낌을 받았습니다. 아무튼 문제를 적당히 잘 이해하고 나면 그냥 1. 수를 k진법으로 변환하고 2. 0을 기준으로 split하고 3. 각 부분 수의 소수 판정하고 이 3가지만 구현하면 됨을 알 수 있습니다.

 
세 가지 각각을 놓고 보면 수학 유형의 문제들에서 다소 기초적인 내용들이기 때문에 크게 어려울건 없지만 소수 판정 부분에서는 약간 실수하기 좋은 부분이 있었습니다. 이 점으로 인해 정답률이 많이 낮지 않았던 것이 아닌가 싶습니다. n = 797161, k = 3인 경우를 생각해보면 부분 수 1111111111111(≓ 2⁴⁰)이 등장하기 때문에 2부터 N-1까지로 나누어보는 방식으로 소수 판정을 O(N)에 하거나 에라토스테네스의 체를 사용할 경우 시간 초과 혹은 런타임 에러가 발생합니다. 대신 나누는 수를 2부터 √𝑁까지 살펴보는 O(√𝑁) 방법으로 소수 판정을 해야 하고 또 int overflow에 주의해야 합니다.

 

코드(C++)

 

코드(Python)

 

코드(Java)