[자바] 프로그래머스 - 순서쌍의 개수 (Lv0, Java)

문제 : Programmers-순서쌍의 개수

문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

필요 알고리즘 개념

• 브루트포스
  
  • n의 크기가 100만밖에 안되므로 그냥 1부터 n까지의 모든 수를 비교해보면 된다. O(n)
• 수학 (정수론)
  
  • 좀 더 효율적으로 O(sqrt(n))으로도 풀 수 있다. 이 경우 수학적 지식이 좀 필요하다.

 

 

풀이

  우선 n의 크기가 100만으로 매우 작으므로 그냥 1부터 n까지의 모든 수를 보면 된다. a를 1부터 n까지 증가시키면서, n%a == 0 이라면 b = n/a 가 되므로 answer을 1 증가시켜주면 된다. 이 경우 O(n)이 걸린다.

int answer = 0;
for (int i = 1; i <= n; i++)
    answer += n%i==0?1:0;

 

---

 

  좀 더 효율적으로 해보려면, 사실 sqrt(n) (n의 제곱근) 까지만 살펴보면 된다. 그 이유는 '에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유' 글에서 확인할 수 있다. 다만 이 경우 케이스가 좀 나뉘어지므로 위보다 계산 로직이 좀 더 복잡해진다. 

case 1 : n%a != 0 이라면 b는 발생되지 않는다.

case 2 : n%a == 0 이고, n%a==sqrt(n) 인 경우라면 예를들어 n=16이었고, 4x4 = 16 인 경우이다. 즉 a와 b가 동일한 경우로 이 경우엔 1개만 카운팅해줘야 한다.

case 3 : n%a == 0이고, n%a!=sqrt(n) 인 경우라면 예를들어 n=20이었고, 4x5 = 20인 경우이다. 즉 a와 b가 동일하지 않은 경우로 a=4, b=5인 경우와 a=5, b=4인 두 가지 경우가 있으므로 2번 카운팅해줘야 한다.

 

  이렇게 짠 경우 O(sqrt(n)) 으로 좀 더 효율적으로 해결 가능하다.

 

코드 : github

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    public int solution(int n) {
        int answer = 0;
        for (int i = 1; i <= Math.sqrt(n); i++)
            answer += n%i==0?(n/i==Math.sqrt(n)?1:2):0;
        return answer;
    }
}