[프로그래머스/Java] Lv.0 순서쌍의 개수

문제

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

- 제한사항

• 1 ≤ n ≤ 1,000,000

풀이

- 오답

테스트 케이스까지 무사히 통과했는데 제출하니까 50.0으로 반이 시간초과로 실패하는 거다. 보통 이런 경우 이중 for문에서 문제가 생기기 때문에 다른 방향의 풀이법을 생각해 봐야겠다고 생각했다.

+) 지금 보니 n의 범위가 1,000,000까지여서 루프를 도는데 많은 시간이 소요되었던 것 같다. 비효율적인 코드였음.

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

- 정답

문제는 약수를 찾는 것이기 때문에 for문의 조건식을 변형해 값을 구해보기로 했다. 내가 이용한 풀이법의 핵심은 다음과 같다.

제곱근과 약수
약수를 찾는 효율적인 방법은 1부터 n까지의 모든 수를 순회하는 것이 아니라 n의 제곱근까지만 순회하는 것이다.
왜냐하면 n의 어떤 수 i가 n의 약수라면, 반드시 n/i도 n의 약수가 되기 때문이다.

ex. n = 36이라면 제곱근 6까지만 체크
→ 36/1 = 몫 : 36, 나머지 : 0 → (1, 36)
→ 36/2 = 몫 : 18, 나머지 : 0 → (2, 18)

이에 따라 조건식을 i*i<=n;으로 변경해 주어진 n의 제곱근까지만 순회하도록 했다. 그리고 n을 i로 나눈 나머지가 0일 때 = 약수일 때, answer++로 카운트 해주었다.

여기서 모든 순서쌍을 구하기 위해 반대의 경우, 예를 들어 (1, 36)과 (36,1)을 모두 카운트 해주기 위해 하나의 조건을 더 추가해야 하는데 이때 변수가 되는 것이 제곱수이다.
예를 들면 (6,6)! 이 경우엔 1번만 카운트 될 수 있도록 조건을 추가해 주어야 한다.(앞선 코드에서 answer+=2; 하지 않은 이유이다.

제곱수는 결국 주어진 n을 i로 나누었을 때 몫이 i가 된다는 것을 의미하므로, if(i != n/i)로 몫이 i가 아닐 때 한 번 더 카운트한다.

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

결과