[프로그래머스-코딩테스트 연습] 소수 찾기

Hi, There!
안녕하세요, 바오밥입니다.

---

목차

• 문제
• 풀이

 

---

문제

문제 내용

https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=java#

프로그래머스

---

 

풀이

나의 풀이

- 아이디어는 바로 떠올랐는데 생각보다 순열 만드는 방법이 너무 어려워서 결국 찾아보았다.

1) 모든 조합의 수 (순서 고려한 순열) 구하기

2) 에라토스테네스의 체 활용해서 소수 여부 확인하기

- 순열 만들 때 재귀 함수를 사용한 풀이가 굉장히 인상적이엿다.

인상적인거랑 별개로 재귀 함수가 엄청 익숙하지는 않아서 이해하는 데 오래걸렸다.

주석은 최대한 자세하게 남겨놓았으니 누군가에게는 도움이 됐으면 좋겠다.

import java.util.*;

class Solution {
//     set 자료구조 생성
    HashSet<Integer> numbersSet = new HashSet<>();

//     순열 재귀 함수
    public void recursive(String comb, String others) {
        if(!comb.equals("")) 
            numbersSet.add(Integer.valueOf(comb));
        
        // 아이디어 : 하나의 조합을 만든 후 다음 전달되는 문자열에서 한 개를 제거
        // 예) 처음에 "", "127"를 호출했으면 "1" 이라는 조합을 만들고 "27"를 매개변수로 전달함.
        // recursive("", "127") -> recursive("1", "27") ... 순으로 실행됨.
        // 만약 for문의 i가 증가하면 시작점이 변경되므로 recursive("2", "17") -> recursive("21", "7") ... 순으로 실행됨.
        for(int i=0; i<others.length(); i++) 
            recursive(comb+others.charAt(i), others.substring(0, i)+others.substring(i+1));
    }
    
    public boolean isPrime(int num) {
        if(num == 0 || num == 1) return false;
        
        int lim = (int)Math.sqrt(num);
        
        for(int i=2; i<=lim; i++)
            if(num%i == 0) return false;
        
        return true;
    }
    
    public int solution(String numbers) {
        recursive("", numbers);
        
        int answer = 0;
        
        Iterator<Integer> it = numbersSet.iterator();
        while(it.hasNext()) {
            int number = it.next();
            if(isPrime(number)) {
                answer++;
            }
        }
        
        return answer;
    }
}