백준 2960 ] 에라토스테네스의 체 / JAVA풀이

문제 설명

에라토스테네스의 체

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

문제 설명

N = 10 K = 7로 입력을 한다면 2,3,4,5,6,7,8,9,10까지의 수가 있고 가장 첫 번째 수인 2를 삭제(K = 1)하고 2의 배수인 4,6,8,10을 차례로 삭제한다.(K = 2,3,4,5) 다 삭제했다면 3,5,7,9가 남아있을텐데, 가장 첫 번째 수인 3을 삭제(K= 6)하고 3의 배수인 9를 차례로 삭제한다.(K=7) 이 때 K ==7이므로 답은 9이다.

답안 소스코드

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

public class Main {
    public static void main(String[] args) {
        // 입력받음 
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();


        //2,3,4...N까지의 수를 저장
        ArrayList<Integer> listN = new ArrayList<>();
        for (int i = 2; i <= N; i++) {
            listN.add(i);
        }

        //답 출력
        System.out.print(recurEpato(listN, K, 0) + "");
    }

    static int recurEpato(ArrayList<Integer> listN, int k, int resultcount) {
        int firstNum = listN.get(0);

        for (int i = 0; i < listN.size(); i++) {
           if (listN.get(i) % firstNum == 0) {
                resultcount++;
                if (resultcount == k) {
                    return listN.get(i);
                }
                listN.remove(i);
            }
        }
        return recurEpato(listN, k, resultcount);
    }
}

소스코드 설명

입력받고 저장하는 것은 문제가 없으니, recurEpato에 대해서만 설명하자면.
재귀를 사용하여 만약 삭제한 횟수가 K인 경우 return하여 답을 출력하고 삭제한 횟수가 K번이 아니라면 같은 패턴을 반복하도록 했다.

    static int recurEpato(ArrayList<Integer> listN, int k, int resultcount) {
        int firstNum = listN.get(0);
    }

가장 첫 번째 값을 받아와서 삭제의 기준(해당 숫자의 배수는 모두 삭제한다)를 세우고,

        for (int i = 0; i < listN.size(); i++) {
           if (listN.get(i) % firstNum == 0) {
                resultcount++;
                if (resultcount == k) {
                    return listN.get(i);
                }
                listN.remove(i);
            }
        }
        return recurEpato(listN, k, resultcount);

남은 요소의 갯수만큼 반복문을 돌려서 모든 요소를 검사하는데, 만약 나누어떨어지는 배수 숫자가 있다면 삭제횟수(resultCount)를 증가시키고 삭제한 횟수가 K번인지 확인 후 맞으면 그대로 반환하고 아니라면 삭제한다.
만약 해당 배수를 다 돌았는데도 여전히 삭제해야할 요소의 갯수가 남았다면 한 번 더 호출하여 다음 단계(다음 배수)를 검사한다.

반드시 답이 있는 문제이며, 답을 찾았을 때 return하며 System.out.print(recurEpato(listN, K, 0) + "");으로 출력된다.