알고리즘 코드카타. 나머지가 1이 되는 수 찾기(2024-06-10)

문제의 개요

요약 : 자연수 n이 주어졌을 때 x로 나눈 나머지가 1인 수 중에서 가장 작은 수를 구하기

 

먼저 n을 x로 나눴을 때 나머지가 1이되는 가장 큰 x는 n-1이다.

 

예시1) n이 10일 때 9로 나누면 나머지가 1

예시2) n이 12일 때 11로 나누면 나머지가 1

 

그렇다면, n-1의 약수 중에서 1을 제외한 가장 작은 수를 구하면 된다.

 

예시1) 10 - 1인 9의 약수 중 가장 작은수는 3이다. -> 10을 3으로 나누면 나머지는 1이다.

예시2) 12 - 1인 11은 약수가 1과 자기자신인 11 뿐인 소수이다 -> 가장 작은 숫자는 11이다.

 

따라서 나는 다음과 같은 코드를 작성했다.

 

 

---

문제점)

 

이 코드는 n-1의 정수의 1을 제외한 가장 작은약수를 구하여 반환하고, 없다면(소수라면) n-1을 반환하는 코드이다. 

 

하지만 작성하고 보니 이런 의문이 들었다. 이 코드는 n-1의 약수를 2부터 n-1까지 i가 하나씩 증가하면서 연산한다.

 

그렇다면 n-1이 엄청나게 크면서 그것이 소수라면 시간적 복잡도가 불필요하게 늘어날것이라 생각했다. 결국 약수를 찾지 못한다면 끝까지 진행될테니까

 

---

 

해결법)

어떤 수 n의 약수들은 대칭적이라는 특성이 있다.

 

예시로 36의 약수를 살펴보면 다음과 같다.

1,2,3,4,6,9,12,18,36

 

여기서 대칭적이라는 뜻은 중간값인 6을 기점으로 서로 대칭적으로 곱하면 36이 된다는 것이다.

1 X 36

2 X 18

3 X 12

4 X 9

그리고 

6 x 6 = 36

즉 36의 제곱근인 6까지의 약수만 구한다면 연산을 덜할 수 있다.

 

이걸 소수를 기준으로 예시를 들어보면

 

11의 제곱근은 3.316이 나온다.

 

소수점을 버리면 3이다.

 

1부터 3까지 11에서 나눠본다. 1을 제외하고 나머지가 0이되는 숫자는 없다.

 

그러므로 11은 소수이므로 11을 반환하면 된다.

 

이제 합성수인 15를 예시로 들어보면

 

15의 제곱근 = 3.87

 

소수점을 버려 3

 

15에서 1부터 3까지 나눠 떨어지는 숫자는 1과 3

 

그리고 15의 약수는 다음과 같다

 

1,3,5,15

---

 

이걸 문제에 적용해보자

 

n = 16이며 x로 나누어 떨어지는 수가 1인 수 중에서 가장 작은 수를 구한다.

 

일단 1이 나머지가 되는 가장 큰 수는 15이다. -> 15의 약수 중 1을 제외한 가장 작은 수를 반환하면 된다.

 

15의 제곱근 = 3.87

 

소수점을 버리면 3 즉, 2부터 3까지 15에서 나누어 떨어지는 수는 3 즉 3은 15의 가장 작은 약수

 

그러므로 16에서 3을 나눈 나머지는 1이다.

 

그러므로 3을 반환한다.

 

소수의 경우 1을 제외하면 나누어떨어지지 않을 것이기에 n-1을 바로 반환하면 된다.

 

---

 

개선 전 코드

개선 후 코드

빨간 박스의 Math.sqrt(n-1) 메서드는 인수의 제곱근을 구하는 기능을 한다. 즉 n-1의 제곱근까지만 계산한다.

 

그리고 n-1을 2부터 제곱근까지 나누어 떨어지는 수가 있다면 그 수를 반환한다.

 

만약 없다면 n-1은 소수이니 n-1을 반환한다.