[프로그래머스, Level 2] 소수 찾기(JAVA)

안녕하세요.

배당 줍는 다람쥐입니다.

 

요즘 다른 회사로 이직을 하고 싶다는 마음이 생겨서,

코딩테스트를 준비하고 있는데, 

예전같이 문제가 잘 풀리지는 않네요...ㅠ

 

그래도 제가 푼 문제와 문제풀이 방법을 이 곳에 꾸준히 올려보고자 합니다.

 

그럼, 프로그래머스 Level 2, 소수찾기 문제풀이를 시작하겠습니다.

출바알

---

문제

프로그래머스 출처 : https://programmers.co.kr/learn/courses/30/lessons/42839

사이트 주소는 아래와 같습니다.

https://programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

 

문제풀이

import java.util.HashSet;

class Solution {
	public int solution(String numbers) {
        HashSet<Integer> set = new HashSet<>();
        
        // 1. 종이 조각의 순열 조합을 만든다.
        permutation("", numbers, set);
        
        // 2. 1에서 만들어진 순열 조합을 가지고 소수인지 판별한다.
        int count = 0;
        while(set.iterator().hasNext())
        {
            int num = set.iterator().next();
            
            set.remove(num);
            
            if(num == 2)
            {
                count++;
            }
            
            if(num % 2 != 0 && isPrime(num))
            {
                count++;
            }
        }
        
        return count;
    }
    
    public boolean isPrime(int n)
    {
        if(n == 0 || n == 1)
        {
            return false;
        }
        for(int i = 3; i <= (int)Math.sqrt(n); i+=2)
        {
            if(n % i == 0)
            {
                return false;
            }
        }
        return true;
    }
    
    public void permutation(String prefix, String str, HashSet<Integer> set)
    {
        int n = str.length();
        
        if(!prefix.equals(""))
        {
            set.add(Integer.valueOf(prefix));
        }
        
        for(int i = 0; i < n; i++)
        {
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);
        }
    }
}}

해당 문제의 풀이 방식에 대해 접근 할 때,

저는 크게 2가지로 분류하였습니다.

 

1. 문제 나오는 종이 조각에 대해 순열 조합을 만든다.

2. 만들어진 순열 조합에서 소수인지 여부를 판별하여 결과값을 도출한다.

 

하여, 아래와 같이 코드를 작성해보았습니다.

순열을 구하는 재귀 알고리즘 방법 같은 경우는 코딩 테스트에서 자주 나올 수 있으니,

한 번쯤 공부해보시는 것을 추천드립니다. :)

 

저도 오랜만에 해보니, 헷갈려서 다른 분들의 블로그에서 순열 조합하는 것을 참고하여 문제를 풀었습니다.ㅠㅠ

 

오늘도 제 블로그 글을 봐주셔서 감사합니다.

 

다음부터는 이런 말보다는 문제와 풀이 방식 위주로 간단하게 올리게 될 것 같습니다.

그럼 안뇽~