[백준][JAVA] 2960번 에라토스테네스의 체

주어진 알고리즘을 구현하는 것이 목표이며, 이번엔 arrayList 함수를 사용하는 것과 사용하지 않는 것으로 두가지 방법 모두로 코드를 작성하려한다.

 

방법1. arrayList함수를 사용하지 않고 구현

이미 알고리즘은 주어져있으므로 크게 생각할 부분은 없지만 array를 생성할때 2~N까지의 수를 집어넣는 것이므로 index에 주의해주어야한다. 1) N의 크기의 array를 생성해 0과 1번째는 사용하지 않는 방법과 2) N-2크기의 array를 생성하되 array에 저장하는 값을 2~N으로하는 방법도 존재하지만, 나는 boolean array를 이용하여 코드를 작성하였다. boolean은 int에 비해 현저하게 작은 메모리를 사용한다는 데에 장점이 있지만, index를 하는 데에 헷갈린다는 단점이 있다.

특히, index += (smallestIdx + 2) 의 부분은 smallestIdx는 인덱스값이고 + 2 한 값이 해당 인덱스에 저장된 숫자이므로, 반복적으로 더하면서 해당 숫자의 배수를 나타낸 것이다. 다시 arr[index - 2]를 통해서 해당 값이 지워졌는지의 여부를 확인할 수 있다.

 

방법2. arrayList함수를 이용하여 구현

방법 1에 비해 자바에 구현된 함수를 이용하므로 더 쉽게 구현할 수 있다. 가장 큰 장점은 index로 접근하지 않아도, 해당 값만으로 제거를 할 수 있다는 것이다. 주의할 점은

remove 메소드에는 파라미터에 따른 2개의 방식이 있다.

1. remove(객체)
2. remove(인덱스)

즉 int로 구성된 arrayList의 경우 arrayList.remove(1)의 형식으로 작성하면 element가 1인 것이 없어지는 것이 아니라, index가 1인 어레이리스트의 두번째 값이 제거되게 된다. 그러므로 값을 이용하여 제거할 경우 코드에서 처럼 list_.remove(new Integer(mulipledP)); 와 같이 인트를 객체로 만들어주어야한다.

 

전체 코드

1. 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();
	    boolean[] arr = new boolean[N-1];
	    for (int i = 0 ; i < N - 1; i++) {
	        arr[i] = true;
	    }
	    int cnt = 0;
	    int smallestIdx = 0;
	    while (cnt < N - 1) {
	        while (true) {
	            
	            if (arr[smallestIdx]) {
	                break;
	            } else {
	                smallestIdx++;
	            }
	        }
	        
	        int index = smallestIdx + 2;
	        while (index <= N) {
	            if (arr[index - 2]) {
	                arr[index - 2] = false;
	                cnt++;
	            }
	            if (cnt == K) {
	                System.out.println(index);
	                return;
	            }
	            index += (smallestIdx+2);
	        }
	    } 
	}
}

2. arrayList함수를 사용한 코드

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

public class Main
{
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    int N = sc.nextInt();
	    int K = sc.nextInt();
	    int cnt = 0;
        ArrayList<Integer> list_ = new ArrayList<Integer>();
        for (int i = 2; i <= N; i++) {
            list_.add(i);
        }
        
        while(list_.size() != 0) {
            int P = list_.get(0);
            int mulipledP = 0;
            while (mulipledP <= N) {
            	mulipledP += P;
                if (list_.contains(mulipledP)) {
                	cnt++;
                    if (cnt == K) {
                        System.out.println(mulipledP);
                    } else {
                        list_.remove(new Integer(mulipledP));
                    }
                }
            }
        }
    }
}

 

 

결과화면