문제 : 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;
}
}
'PS > Programmers' 카테고리의 다른 글
[자바] 프로그래머스 - 올바른 괄호 (Lv2, Java) (0) | 2023.01.29 |
---|---|
[자바] 프로그래머스 - 겹치는 선분의 길이 (Lv0, Java) (2) | 2022.12.07 |
[자바] 프로그래머스 - 다음에 올 숫자 (Lv0, Java) (0) | 2022.11.25 |
[자바] 프로그래머스 - 종이 자르기 (Lv0, Java) (0) | 2022.10.19 |
[자바] 프로그래머스 - 쿠키 구입 (Lv4, Java) (0) | 2022.10.14 |
댓글