[JAVA]프로그래머스 - 순서쌍의 개수

https://school.programmers.co.kr/learn/courses/30/lessons/120836

프로그래머스

문제

순서쌍이란 두 개의 숫자를 순서를 정하여 짝지어 나타낸 쌍으로 (a, b)로 표기합니다. 자연수 n이 매개변수로 주어질 때 두 숫자의 곱이 n인 자연수 순서쌍의 개수를 return하도록 solution 함수를 완성해주세요.

 

풀이

두 숫자의 곱이 n인 자연수 순서쌍의 개수를 구하는 문제이다.

이 문제는 크게 두 가지 방법으로 풀 수 있다.

 

1. 반복문을 1부터 n까지 돌려서 모든 경우의 수 찾기

사실 이 방법의 코드가 훨씬 간단하다. 아래 코드를 보면 바로 이해가 될 것이다.

for(int i = 1; i <= n; i++) {
    if(n % i == 0) answer++;
}

 

2. 반복문을 1부터 루트 n까지 돌려서 (a, b) 순서쌍 중 a <= b인 순서쌍만 찾기

필자는 이 방법으로 문제를 풀어보았다.

 

1번과 2번 방법의 차이를 예를 들어보겠다.

ex) n = 20일 경우

1번 방법 : (1, 20), (2, 10), (4, 5), (5, 4), (10, 2), (20, 1)처럼 모든 경우를 찾고, 6을 return 한다.

2번 방법 : (1, 20), (2, 10), (4, 5)까지 찾고, 찾을 때마다 2씩 더하여 6을 return 한다.

 

그런데 왜 반복문을 루트 n까지 돌리는지 궁금할 수 있다.

반복문에서 i를 순서쌍의 a로, (n % i)를 순서쌍의 b로 생각하면 이해가 될 것이다.

a <= b인 경우만 찾고 있는데, 루트 n보다 큰 값을 a(= i)로 설정하게 되면 b가 더 작아지는 경우가 생기기 때문이다.

 

if(i == Math.sqrt(n)) answer--;

위 코드 이해가 안 되는 분들도 계실 텐데, 이 경우는 a와 b가 같은 경우라고 생각하면 이해가 될 것이다.

a와 b가 같으면 (a, b)와 (b, a)는 한 가지 경우이기 때문에 answer에서 1을 빼준 것이다.

 

2번 방법이 조금 더 복잡하지만, 1번 방법보다 반복문을 훨씬 적게 돌리기 때문에 성능이 좋다는 장점이 있다.

 

코드

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

틀린 부분이 있다면 정정해 주시면 감사하겠습니다.
궁금한 부분이 있거나, 다른 아이디어가 있으시면 자유롭게 댓글 남겨주세요!