[백준/BOJ] 11653번 : 소인수분해 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

https://www.acmicpc.net/problem/11653

11653번: 소인수분해

---

- 문제 -

 

난이도 실버 5 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

소인수분해는 1보다 큰 자연수들의 곱으로 나타내는 수이다. 말그대로 주어진 값을 1보다 큰 수 2부터 시작해서 1이 될때까지 나누면 된다는 것이다. 방법은 매우 쉽다. 2부터 시작해서 해당 값으로 나누어 떨어지면 나누고, 다음 수도 나누어 떨어지는지 확인한다. 2로 나누어 떨어지지 않는다면 다음 자연수인 3으로 나누어떨어지는지 확인한다. 나누어떨어지면 나누고, 나누어쩔어지지 않으면 +1을 해서 위 과정을 반복한다. 그렇게 주어진 값이 1이 될때까지 반복하고, 나눈 값들을 전부 출력한다.

예제 1을 보면 72이다. 2로 먼저 나누어보자. 나누어 떨어진다. 그럼 72 / 2 = 36이 된다. 다음 36을 본다. 2로 나누어 떨어지니 36 / 2 = 18이 된다. 18도 2로 나누어 떨어지니 18 / 2 = 9가 된다. 9는 2로 나누어떨어지지 않으니 2+1 해서 3을 본다. 9는 3으로 나누어 떨어지니 9 / 3 = 3이 된다. 3도 3으로 나누어 떨어지니 3 / 3 = 1이 된다. 입력된 값이 1이 되었으니 반복을 종료하고, 나눈 값들을 출력하자. 2, 2, 2, 3, 3으로 나누었으니 해당 값들이 출력 값이 되는 것이다.

 

원래 소인수분해에서 소인수는 소수들로만 이루어져있다. 그렇다면 나누는 값들을 소수 판별해서 해야하지 않나? 하지만 앞에서 소수 2로 나누어지지 않는 값이라면 소수가 아닌 4로는 당연 나누어 떨어지지 않을 것이고, 3으로 나누어 떨어지지 않는다면 6이나 9로 당연히 나누지 못할 것이다. 그렇다고 +1로 모든 경우를 보기에는 1000만이란 값은 충분했지만, 더 많은 특히 상당한 자릿수의 소수가 주어진다면 시간 안에 처리 하지 못할 것이다.

 

코드를 보자.

 

---

-풀이-

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		//나눠줄 값 i
		int i = 2;
		//N이 1이 아니라면 반복
		while(N != 1) {
			//나누어 떨어지면 나눈 값을 출력하고, N을 i로 나눠준다.
			if(N % i == 0) {
				System.out.println(i);
				N /= i;
			//나누어 떨어지지 않는다면 i +1해준다.
			}else {
				i++;
			}
		}
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.