백준알고리즘 2501번 약수 구하기 C#

세부 정보

• 사이트: 백준알고리즘
• 번호: 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을 출력하시오.

 

풀이

배열 리스트를 사용하면 n개의 공간을 가지는 배열을 만들 필요가 없으며 값이 저장되지 않아 메모리 공간이 노는 일이 없다.

using System.Collections;
using System.Text;

StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
StringBuilder sb = new StringBuilder();

// 약수들을 저장할 배열 리스트 선언
ArrayList arrayList = new ArrayList();
// 자연수 n과 k를 입력받는다
int[] nk = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);

// 약수 구하는 과정
for (int i = 1; i <= nk[0]; i++)
{
    // 입력한 숫자 n을 1부터 n까지의 수로 나누어서 나머지가 없으면
    if (nk[0] % i == 0)
        // 약수인 몫을 배열 리스트에 추가
        arrayList.Add(nk[0] / i);
}

// n의 약수의 개수가 k보다 작을 때는 0 출력
if (arrayList.Count < nk[1])
    sw.WriteLine("0");
else // 배열에서 i번째로 작은 수 출력
    sw.WriteLine(arrayList[arrayList.Count - nk[1]]);

sr.Close();
sw.Close();

 

후기

이 문제는 StringBuilder 연습용으로 풀어본 문제였다. 중간에 약수들을 스택에 저장도 해봤고 큐에 저장해 보려고 시도하다가 배열 리스트(Array List)를 사용하는 것으로 가닥을 잡았다. 배열 리스트도 내용물 개수를 셀 때 다른 자료구조처럼 Count를 사용했다. 다만 Array.ConvertAll() 사용이 익숙하지는 않아서 어려움을 겪기도 했다. 전체 중 일부 값을 추출해서 저장해야 할 상황에서는 배열 리스트가 효과적이다.