[백준] 2501번 - 약수 구하기 C++

문제

어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다. 
6을 예로 들면
6 ÷ 1 = 6 … 0
6 ÷ 2 = 3 … 0
6 ÷ 3 = 2 … 0
6 ÷ 4 = 1 … 2
6 ÷ 5 = 1 … 1
6 ÷ 6 = 1 … 0
그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다.
두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.

출력

첫째 줄에 N의 약수들 중 K번째로 작은 수를 출력한다. 만일 N의 약수의 개수가 K개보다 적어서 K번째 약수가 존재하지 않을 경우에는 0을 출력하시오.

---

풀기전 로직 생각

1. N과 K를 입력받고 약수인 factor와 count변수를 각각 1과 0으로 초기화시켜 선언한다.
2. 반복문을 통해 약수값인 factor로 1개씩 증가시킨다.
3. factor로 N을 나눈 나머지가 0이면 그 factor는 N의 약수이므로 count를 증가시킨다.
4. 만약 증가된 카운트가 입력받은 K와 같아지면 여태 증가된 factor가 N의 K번째 약수이므로 출력시키고 종료한다.
5. 근데 K값이 count보다 크고 factor가 N보다 크거나 같아지면 0을 출력시키고 종료한다.

코드

#include <iostream>
using namespace std;

int main(){
	
	int N, K;

	cin >> N >> K;

	int factor = 1; //약수 찾기
	int count = 0; //K와 같은지 판별하기위한 카운트변수

	for (	;	;factor++) {

		//약수값이 나올때마다 count를 증가
		if (N % factor == 0)
			count++;

		//카운트가 입력받은 K번째 값과 똑같아지면 해당 factor변수가 N의 K번째 약수
		if (count == K) {
			cout << factor;
			break;
		}

		//입력받은 K가 카운트된 약수 개수보다 크고, 증가된 약수가 입력받은 N보다 크거나 같아질경우 0출력
		else if (K > count && factor >= N) {
			cout << "0";
			break;
		}
	}
}

두번째 코드

반복문이 깔끔하지 않아서 다시 로직을 구현해보았습니다.

1. 반복문에 factor를 1부터 시작시켜서 N까지 증가되도록 하며 factor는 1씩 증가시킨다.
2. 만약 N을 factor로 나눈 나머지가 0이면 해당 factor는 약수이다.
3. 우선 count를 증가시키고 count와K가 같아지면 그때 factor가 N의 K번째 약수이므로 해당 factor를 출력하고 종료.
4. 반복문이 끝날때까지 출력이 안됐다면 그냥 0으로 출력시키며 종료.

#include <iostream>
using namespace std;

int main() {

	int N, K;

	cin >> N >> K;

	int count = 0; //K와 같은지 판별하기위한 카운트변수

	for (int factor = 1; factor <= N; factor++) {
		if (N % factor == 0) { //약수값을 찾았을때
			count++; //카운트를 증가시키고
			if (count == K) //해당 카운트가 K와 같아지면
			{ //그 증가된 factor가 N의 K번째 약수값
				cout << factor;
				return 0;
			}
		}
	}

	cout << "0";
	return 0;
}

결과

 

아래가 첫번째코드 위에가 두번째 코드로 제출한 결과입니다.

 

시간복잡도는 서로 0(N)이고 성능차이도 미미하지만 두번째 코드가 직관적이고 명확하네요.