정올 2809 약수 (JAVA 자바)

문제 출처 - http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=450&sca=2030 

JUNGOL

 

문제

한 개의 정수를 입력받아 입력받은 정수의 약수를 모두 출력하는 프로그램을 작성하시오.

 

---

 

 

입력형식

정수 N이 주어진다. (2 ≤ N ≤ 21억)

 

---

 

출력형식

N의 약수를 작은 수부터 차례로 모두 출력한다.

 

---

코드

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

public class JO28091_약수 {
	static ArrayList<Integer> list;
	static int N;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		list = new ArrayList<>();
		for (int i = 1; i * i <= N; i++) {
			if(N % i == 0) {
				list.add(i);
				
				if(N / i != i) {
					list.add(N / i);
				}
			}
		}
		
		Collections.sort(list);
		for (int i = 0; i < list.size(); i++) {
			System.out.print(list.get(i) + " ");
		}
	}
}

 

문제에서 입력이 21억까지 들어올 수 있다고 되어있다. 따라서 21억은 int형 범위에 들어가므로 long을 사용할 필요는 없다. 그러나 21억이라는 수를 매번 N % i 해서 21억번 비교하게 되면 당연히 시간 초과가 날 것이다. 따라서 제곱근을 사용하여 약수를 구해주는 방법이 현명하다. 또한 arraylist를 사용하여 정렬할 때 collections.sort를 사용하였는데, 이는 collection의 sort가 퀵정렬을 사용하기 때문이다. 만약 배열을 크게 주고 정렬을 하게 된다면 직접 퀵소트를 구현하는 방법도 괜찮을 것 같다. 

 

친절하게 문제 밑에 해결 방법 힌트가 나와있는데 사실 이거 읽어도 해결할 수 있을 것 같다. 정렬만 하면 된다.