[코딩테스트] 소수판변 반복문의 범위

문제 : 백준 1978번 소수 찾기

 

다른사람 풀이

코테 문제를 풀면 항상 다른 사람들 풀이를 보고 있는데

정말 생각지도 못한 방법을 한번씩 보게 되어서 놀랄 때가 있다.

 

사실 그냥 수학적으로 깊게 생각해보면 알... 수 없다.. 

정말 이런 방식은 스스로 떠올리는게 아니라 이런 방법이 있다는 사실을 외우는게 맞는 방법같다.

 

내 코드는 크게 중요치 않으니 넘어가고 놀랐던 코드이다.

// https://www.acmicpc.net/source/83579484
public class Main {
    static int N;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int cnt = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            if(isPrime(num)) cnt++;
        }
        System.out.println(cnt);
    }
    private static boolean isPrime(int num) {
        if(num == 1) return false;
        for(int i=2;i*i<=num;i++){
            if(num%i == 0) return false;
        }
        return true;
    }
}

 

해당 코드에서 나는 isPrime을 구한 저 반복문의 범위에서 당황했다..

처음 봤을때 도대체 왜 저렇게 한건지 머리에 떠오르지가 않았기 때문이다.

 

소수판별 반복문의 범위

 private static boolean isPrime(int num) {
    if(num == 1) return false;
    for(int i=2;i*i<=num;i++){
        if(num%i == 0) return false;
    }
    return true;
}

 

이부분이다.

num == 1일때 1은 소수가 아니므로 false를 반환하는 건 ok.

 

for문에서 i 가 2부터 i * i <= num 까지 실행하면서

i 로 나누어떨어진다면 false를 반환하는 것이다.

 

false를 반환하는건 이해가 되지만 왜 i * i 까지만 해도 되는거지??

머리가 돌아가지 않았다.

 

간단히 생각해야한다. 머리아프다.

어떤수의 제곱보다 같거나 작을 때까지 해당 수가 약수인지 확인하는 이유는

나누는 값과, 나누어 떨어진 결과(몫)이 세트이기 때문이다.

나누는 값 x 몫 = num 인 값과 몫을 찾는 것이다.

 

100을 예로 들어보자

100을 두 수의 곱으로 표현하면 아래와 같다

1	100
2	50
5	20
10	10
20	5
50	2
100	1

 

이렇게가 100을 만드는 두 수의 곱이다.

10 * 10을 기준으로 그냥 순서만 바뀐다는 것을 알 수 있다.

다른 것도 해보겠다

 

88을 한번 해보자

1	88
2	44
4	22
8	11
11	8
22	4
44	2
88	1

 

중간에 좌우의 수가 반전되는 순간이 있다.

왼쪽이 8일때 인데, 8은 √88인 9.38... 보다 작은 수이다.

 

그 이상으로 넘어갈 때는 그냥 순서만 바뀌고 같은 값들의 조합이 나오는 것이다.

 

이제는 모두들 이해가 됐을 것이라고 생각한다.

 

그러니까 88은 9.38...보다 같거나 작은수 까지만 확인하면 되는거고

100은 10보다 같거나 작은수 까지만 확인하면 된다는 말이다.

 

1로는 어떤 수든 나누어 떨어지므로 나누는 수는 2부터 시작하고,

input이 1로 들어왔을 경우에 1은 소수가 아니므로 제외하는 것이다.

 

private static boolean isPrime(int num) {
    if(num == 1) return false;
    for(int i = 2; i * i <= num; i++){
        if(num % i == 0) return false;
    }
    return true;
}

 

이제 코드를 다시보면 이해가 된다.

 

그니까 num이 100일 때 나는 지금까지 50번을 반복시키면서 값을 찾았는데

10번만 반복하면 끝난다는 충격적인 사실을 깨닳은 것이다..ㅎ

 

---

활용 : 약수 찾기

이걸 알고나서 그럼 지금까지 약수 구하는 문제도 이런식으로 반복을 줄일 수 있었겠구나 싶다.

 

package no_1978;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Divisor_test {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		List<Integer> divisors = new ArrayList<>();
		
		for(int i = 1; i*i <= N; i++){
			if(N % i == 0){
				divisors.add(i);
				divisors.add(N / i);
			}
		}
		// divisors => N의 약수들의 리스트
		
		StringBuilder sb = new StringBuilder();
		divisors.sort(Comparator.naturalOrder());
		for(int i = 0; i < divisors.size(); i++) {
			sb.append(divisors.get(i).toString()).append(" ");
		}
		System.out.println(sb);
	}
}

 

이렇게하면 반복을 훨씬 적게 하면서 약수들을 출력할 수 있는 것 같다.

한번씩 이렇게 생각지 못한 풀이가 나오면 당황스럽고, 세상에 무서운 사람들이 참 많구나 싶으면서도

한편으로는 이런 방법을 배울 수 있어서 기쁘기도 하다.

 

 

아직까지 매일 코테 풀기를 착실히 하고있는데 정말 많은 공부가 되는 것 같아서 좋다.

앞으로도 가능하면 취업 이후에도 꾸준히 진행해볼 계획이다.

화이팅!!

 

---

[ 추가내용 ]

범위가 위에서는 for ( int i = 1; i * i <= N; i++) { } 로 사용하고 있는데

Math 라이브러리에 있는 sqrt( ) 라는 제곱근을 구할 수 있는 메서드를 활용하면 아래와같이도 표현이 가능하다

for ( int i = 1; i <= Math.sqrt(N); i++) { }

 

표현방식만 다르고 의미는 동일하다

i의 제곱이 N보다 작거나 같은 것인가

i가 N의 제곱근보다 작거나 같을 것인가

 

sqrt => square root => 제곱 근