[Java] 소수 찾기 (소수 판별 & 문자열 조합 & Iterator)

재귀를 활용한 문자열 조합과, 소수 판별은 언젠가 또 이용될 거 같으니 꼭 다시 복습하기!

문제 링크

문제

• 주어진 숫자를 이용하여 모든 조합의 숫자를 구한 뒤, 소수의 개수를 출력

풀이

1. 모든 문자열의 조합으로 만들 수 있는 숫자들 생성
   1. 1 숫자의 중복을 없애기 위해 HashSet 사용하여 중복 제거
2. HashSet 안에 담긴 숫자들에 대해 소수를 판별하여 카운팅

재귀를 활용한 문자열 조합

재귀 메서드의 매개변수로 조합된 문자열과, 남은 문자열을 전달하며 모든 문자열이 반복되도록 한다.

public void recursive(String comb, String others) {
        if (!comb.equals("")) { // 첫 로직 실행 시 빈 문자열이므로 이를 넘기기 위함
            numbersSet.add(Integer.valueOf(comb));
        }
        
        for (int i = 0; i < others.length(); i++) {
            recursive(comb + others.charAt(i), 
                      others.substring(0,i) + others.substring(i + 1));
        }
    }

• 반복문 안을 보면 조합이 필요한 모든 문자열의 갯수 만큼 반복한다.(그래야 모든 수를 사용하기에)
• 반복할 때 조합된 문자열과 새롭게 조합할 문자열을 붙인다.

for (int i = 0; i < others.length(); i++) {
            recursive(comb + others.charAt(i), 

• 그 다음, 재귀로 넘길 때 조합한 문자를 제외한 나머지 문자를 같이 전달한다. 이 때, subsString 을 활용하여 조합에 사용된 해당 문자의 앞 부분 과 뒷 부분 을 자른다.

recursive(comb + others.charAt(i), 
                      others.substring(0,i) + others.substring(i + 1));

---

소수 판별

• 첫 번째, 0 과 1 은 소수가 아니다.
• 두 번째, 판별할 숫자에 루트를 한 값이 2 이상의 숫자에 의해 나누어 떨어지면 소수가 아니다.

 private static boolean isPrime(int index) {
		if (index == 1 || index == 0) {
			return false;
		}
		
		int lim = (int)Math.sqrt(index);
		for (int i = 2; i <= lim; i++) {
			if (index % i == 0) {
				return false;
			}
		}
		
		return true;
	}

• lim 이란 변수에 Math.sqrt() 한 값을 넣어 활용한다. (루트 연산한 값)
• 2 부터 lim 이하의 숫자를 반복하며, 0으로 나누어 떨어지는지 탐색한다.

---

Iterator

ArrayList, HashSet과 같은 컬렉션을 반복하는 데 사용할 수 있는 객체.

Iterator<Integer> it = numbersSet.iterator();

처럼 선언하며 hasNext() 와 같이 활용한다.