[프로그래머스] 소수 찾기

프로그래머스 소수 찾기를 풀어보았습니다.

 

링크

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

프로그래머스

 

문제

 

풀이

모든 수의 조합을 만들고 그 중에서 소수 갯수를 반환합니다.
1. 모든 수의 조합 생성
2. 소수 갯수 반환

 

---

 

1. 모든 수의 조합 생성
createdNumber 함수에 모든 수의 조합을 생성하는 로직을 만들었습니다.
재귀함수를 이용하여 모든 수의 조합을 만들었습니다.

HashSet<Integer> set = new HashSet<>();

public void createdNumber(String com, String numbers) {
    if (!"".equals(com)) set.add(Integer.parseInt(com));
    for (int i = 0; i < numbers.length(); i++) {
        if (!"".equals(com)) set.add(Integer.parseInt(com));
        createdNumber(com + numbers.charAt(i), numbers.substring(0, i) + numbers.substring(i+1));
    }
}

....
....

반복문을 사용하여 모든 경우의 수를 생성합니다.
이 때 중복되는 수가 있으니 set을 이용하여 중복은 제거합니다.

con 값이 공백이 아닐경우 set에 담아줍니다.

if (!"".equals(com)) set.add(Integer.parseInt(com));

이 if문이 두 번 똑같이 나와서 setCom 함수로 따로 만들었습니다.

public void setCom(String com) {
    if (!"".equals(com)) set.add(Integer.parseInt(com));
}

public void createdNumber(String com, String numbers) {
    setCom(com);
    for (int i = 0; i < numbers.length(); i++) {
        setCom(com);
        createdNumber(com + numbers.charAt(i), numbers.substring(0, i) + numbers.substring(i+1));
    }
}

 

 

2. 소수 갯수 반환
중복을 제거한 수의 조합 중에 소수인 수의 갯수를 반환합니다.
스트림의 filter를 이용하여 소수인 수만 count 하였습니다.

// 2. 소수 갯수 반환
return (int) set.stream().filter(n -> isPrime(n)).count();

 

isPrime 함수는 소수인지 판별해주는 함수입니다.

public boolean isPrime(int num) {
    if (num < 2) return false;

    int limit = (int) Math.sqrt(num);

    for (int i = 2; i <= limit; i++)
        if (num % i == 0)
            return false;

    return true;
}

 

전체코드

HashSet<Integer> set = new HashSet<>();

public boolean isPrime(int num) {
    if (num < 2) return false;

    int limit = (int) Math.sqrt(num);

    for (int i = 2; i <= limit; i++)
        if (num % i == 0)
            return false;

    return true;
}

public void setCom(String com) {
    if (!"".equals(com)) set.add(Integer.parseInt(com));
}

public void createdNumber(String com, String numbers) {
    setCom(com);
    for (int i = 0; i < numbers.length(); i++) {
        setCom(com);
        createdNumber(com + numbers.charAt(i), numbers.substring(0, i) + numbers.substring(i+1));
    }
}

public int solution(String numbers) {
    // 1. 모든 수의 조합 생성
    createdNumber("", numbers);

    // 2. 소수 갯수 반환
    return (int) set.stream().filter(n -> isPrime(n)).count();
}

 

후기

* 난이도 (5점 만점)

5 : 풀 줄 알면 기업 코딩 테스트는 문제없음.

4 : 평균적인 기업 코딩 테스트의 중간 이상.

3 : 평균적인 기업 코딩테스트의 쉬운 문제.

2 : 알고리즘 문제를 연습하고 있다면 풀 수 있는 문제.

1 : 시간이 오래 걸리지 않고, 누구나 풀 수 있는 문제.

 

프로그래머스의 소수 찾기 문제는 완전탐색에 대해 공부가 필요한 문제입니다.
완전탐색을 공부하여 모든 수의 조합을 생성하고 소수를 판별하여 갯수만 반환해주면 됩니다.
완전탐색 + 소수판별.