Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- EditorInfo
- 순수함수
- Kotlin
- 프로그래머스
- 시뮬레이션
- imeOptions
- 조합
- hilt
- 최단경로
- 백준 14501
- 백준
- 오르막수
- SWEA
- 스카이라인 쉬운거
- Android
- 자바
- dfs
- BuildConfig
- 백준 퇴사
- 약수 구하기
- Parcelize
- EditText
- val
- 완전탐색
- 지능형 기차2
- Parcelable
- java
- 2501
- BFS
- 순열
Archives
- Today
- Total
안드 공부를 해볼까?
[Java] 약수 구하기 본문
728x90
1. 개요
약수 구하는 방법은 기본적으로 그 수와 나눠서 나머지가 없다면 그것은 약수가 됩니다.
하지만 우리는 더 새로운 방법을 찾아봅시다.
2. 본문
만약 우리가 약수를 구한다고 할 때 단순히 생각나는 것은 약수를 전부다 구하는 것 입니다.
하지만 21억의 약수를 구한다고 하면 21억번을 반복해야할까요?
int num = Integer.parseInt(st.nextToken());
int pos = Integer.parseInt(st.nextToken());
ArrayList<Integer> list = new ArrayList<>();
for(int i = 1; i<=num; i++){
if(num % i == 0) list.add(i);
}
if(list.size() < pos) System.out.println(0);
else System.out.println(list.get(pos-1));
정말 간단하게 생각하면 이렇게 풀면 될 것 입니다.
하지만 더 효율적인 방법으로 해볼까요?
int num = Integer.parseInt(st.nextToken());
int pos = Integer.parseInt(st.nextToken());
ArrayList<Integer> list = new ArrayList<>();
// 제곱근 생성
int repeat = (int) Math.sqrt(num);
for (int i = 1; i <= repeat; i++) {
if (num % i == 0) {
list.add(i);
if (num / i != i) list.add(num / i);
}
}
Collections.sort(list);
if (list.size() < pos) System.out.println(0);
else System.out.println(list.get(pos-1));
바로 제곱근을 통해 약수를 구하는 방법입니다. 이렇게 되면 반복횟수의 제곱근 만큼만 반복하죠.
1. 1 ~ 제곱근 만큼 반복하기
2. 만약 num을 i로 나눈 나머지가 0이라면 -> 약수
3. 추가로 num을 i로 나누면? -> i에 대응하는 수 -> 약수 (하지만 중복처리를 위해 num / i != i)
간단하게 12를 예로 들어보겠습니다.
12 = 1 2 3 4 6 12, 제곱근은 3.xxxx
1과 대응하는 숫자는 12, 2와 대응하는 숫자는 6, 3과 대응하는 숫자는 4가 됩니다.
반면에 25를 예로 들어볼까요?
25 = 1 5 25, 제곱근은 5
1과 대응하는 숫자는 25, 5와 대응하는 숫자는 5입니다. 25 / 5 = 5 이기 때문에 중복처리를 해줘야 하죠.
3. 문제
https://www.acmicpc.net/problem/2501
해당 문제에서는 제곱근으로 구해도 되고 전체 숫자를 반복해도 풀립니다.
하지만 반복횟수가 더 작은 제곱근으로 푸는 것이 더 좋겠죠?
반응형
'알고리즘 > 지식' 카테고리의 다른 글
[Kotlin] 최소, 최대 (0) | 2023.02.24 |
---|---|
[Java] 이진수 (0) | 2023.02.21 |
Comments