[프로그래머스] 코딩테스트 입문 : 순서쌍의 개수

| 문제

순서쌍이란 두 개의 숫자를 순서를 정하여 짝지어 나타낸 쌍으로(a,b)로 표기합니다.

자연수 n이 매개변수로 주어질 때 두 숫자의 곱이 n인 자연수 순서쌍의 개수를 return하도록 solution 함수를 완성해주세요.

| 제한 사항

• 1 ≤ n ≤ 1,000,000 

| 입출력 예

n	result
20	6
100	9

| 힌트

두 숫자의 곱이 n이면 둘 중에 하나의 숫자로 n을 나눴을 때 나머지가 0입니다.

| 풀이 1

힌트에서 제시한대로 특정 숫자 i를 n으로 나눴을때 나머지가 0인 숫자의 개수를 구했습니다.

주어진 숫자가 20일 경우 순서쌍이 (1,20),(2,10),(4,5),(5,4),(10,2),(20,1)로 총 6라면 우리는 두개의 순서쌍 중에서 앞에 오는 숫자만 구해준 것이죠.

public class Solution {
	public int solution(int n) {
		int answer = 0;
		for(int i = 1 ; i <= n ; i++) {
			if(n%i == 0) answer++;
		}
		return answer;
	}
}

| 풀이 2

풀이 1에서 이미 눈치채신 분들도 있겠지만

순서쌍은 주어진 숫자 n의 제곱근을 기준으로 삼을때

양쪽이 데칼코마니처럼 같은 수로 이루어져 있습니다.

그러므로 반복문의 기준을 제곱근으로 삼고 절반만 반복하여 소요 시간을 줄일 수 있습니다.

public class Solution {
	public int solution(int n) {
        int answer = 0;
        for(int i = 1; i* i <= n ; i++) {
        	if(i*i == n) answer++;
        	else if(n % i == 0) answer +=2;
        }
        return answer;
    }
}

| 해설

두 풀이법의 전반적인 실행 흐름은 일치합니다.

그러나 풀이 1보다 풀이 2의 반복횟수가 절반정도로 줄어듭니다.

실제로 각각 실행해보면 대부분 케이스의 실행 시간이 절반으로 줄어들고,

심하게는 4.77ms 소요되던 것이 0.05ms로 줄어듭니다.

제곱근을 사용하여 수행 횟수를 줄이는 문제는 종종 나오는 아이디어이므로 잘 기억해두시길 바랍니다.