-
[월간 코드 챌린지 시즌3] 10월 문제 해설이벤트 2021. 10. 18. 17:46
코딩이 재미있는 사람들을 위한 챌린지! 프로그래머스에서 2021년 9월 9일, 10월 7일 두 번에 걸쳐 월간 코드 챌린지 시즌3가 진행되었습니다. 2021년 10월 7일 19시 30분부터 22시 30분까지 진행된 시즌3 10월 문제의 간단한 해설을 공개합니다. [1번 문제] 나머지가 1이 되는 수 찾기 출제 의도 반복문을 활용할 수 있는지 해설 2부터 n-1까지의 모든 수에 대해 n을 해당 수로 나눈 나머지가 1이 되는 지 확인하면 됩니다. 시간복잡도는 $O(n)$ 입니다. 더 빠른 방법 해설 정답을 $p$라고 할 때, $n = pk + 1$ 이므로, $n-1 = pk$ 입니다. 즉, $n-1$의 가장 작은 약수(1 제외)를 찾으면 됩니다. $\sqrt{n}$ 까지의 모든 수를 직접 나눠보는 방식(시간..