[정올 Begginer_Coder - 수학1] 2809.약수_자바JAVA

 

[ 문제 ]  정올 2809.약수

 

문제 링크 : www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=450&sca=2030

JUNGOL

 

 

---

 

[ 입출력 ]

---

 

[ 풀이 ]

 

< 접근 방법 및 풀이 >

• 2<= N <= 21억, N의 범위가 최대 21억이다. 문제에서 제한시간이 1초이므로 약 1억번에 1초이니 N번을 다 돌리면 당연히 시간초과가 난다.
• 정수 N이 주어졌을때, 약수를 구하기 위해 반복을 돌릴 조건이 필요하다. 조건은 힌트에 잘 설명되어있듯이 최대 제곱근까지 반복할 수 있다.
• 문제 예시처럼 N = 24일 경우, for문의 i값은 1<= i <= 4.89~~가 된다.
• 1 * 24, 2 * 12, 3 * 8, 4 * 6  => i는 정수이므로 1~4까지만 반복이 돌아도 약수를 다 구할 수 있다.
• 정답에서 약수는 오름차순으로 정렬하라고 했으므로 1, 2, 3, 4, 6, 8, 12, 24 이다.

 

< 주의할 점 >

• for문 범위 잘 생각하기

---

 

JAVA코드

package 수학1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class 약수_2809 {

	public static void main(String[] args) {
		Scanner sc = new Scanner (System.in);
		int N = sc.nextInt();
		
	
		int arr [] = new int [10000]; 
		int cnt = 0;
		//약수 구하기. N의 범위가 ~21억개이므로 범위 줄이기
		int sq = (int) Math.sqrt(N);
		for (int i = 1; i <= sq; i++) {
			if(N % i == 0) { // i가 약수이면 
					arr[cnt++] = i; //i담고
					if(i != N/i ) {
						arr[cnt++] = N/i;
					}
				
			}
		}
		
		Arrays.sort(arr);
		
		for (int i : arr) {
			if(i != 0) System.out.print(i + " ");
		}
		
		
		
	}

}

---

 

REVIEW

생각보다 오래걸렸다.

기초라고 쉽게 봤는데 생각보다 범위 생각하는 조건을 떠오르는데 시간을 많이 썼다.

처음에는 단순히 24일경우에 for문의 조건을 24를 i로 나누어 떨어지는 몫으로 계속 값을 바꿨는데

1, 24, 2, 12,  3, 8,  4, 6, 6, 4 이런식으로 값이 담겼다. 중복되는 값을 처리하려고 한번 더 검사하고 처리했었는데

애초에 i값이 1~4까지면 이미 약수가 구해진거므로 더 돌릴 필요도 없었고 제곱근이라는 조건을 떠올리기가 어려웠다.

 

그리고 제출하고 틀리면 틀린 예시를 잘 알려줘서 어느부분이 틀렸는지 알 수 있어서 좋았다. 이런 부분에서

정올 기초를 탄탄히 다지라고 하는 것 같다.