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

 

프로그래머스 level2 - 소수 찾기 풀이

---

 

 

 

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

 

 

 

 

 

문제 간단 요약

 

- 문자열로 0~9의 숫자들이 주어진다.

 

- 해당 숫자 하나 하나로 만들 수 있는 모든 조합의 숫자들 중 소수의 개수를 구하라 

 

 

 

 

나의 풀이

 

1. 숫자를 조합해 만든 여러 수들 중 같은 수가 있다면 한번만 카운트해야함.

 

=> Set 사용

 

 

2. 숫자 조합을 만들 때 자기 자신이 들어가면 안된다.

 

 

 

---

예를 들어 입력이 "171" 이면

 

 

숫자 하나에 다른걸 붙여 두자리 수를 만들면 

 

11 17 71

 

 

두 자리수에 한 자리수들을 모두 앞뒤로 붙여 세자리 수를 만든다고 생각했을 때

 

117 711 171 111???

 

 

자기 자신이 포함되어있었던 건지 아닌건지 체크할 방법이 떠오르지가 않았다.

 

 

 

그래서 숫자 문자열을 입력받았을 때 0~9 까지 모두 몇개가 있나 세어주는 배열을 만들고 체크하는 메소드를 활용했다.

 

 

// 입력받을 숫자 1의자리수 총 갯수에 대한 배열
    int[] countArr = new int[10];

 

    /**
     * @param n : 넣을 숫자 문자열
     * @param checkArr : 입력받은 숫자 문자열들 0~9까지의 count 배열
     * @return true: set에 넣어도 되는 숫자다.
     */
    private static boolean checkNumLimit(String n, int[] checkArr) {
        for (int i = 0; i < n.length(); i++) {
            char c = n.charAt(i);
            if (n.chars().filter(v -> c == v).count() > checkArr[c - 48]) {
                return false;
            }
        }
        return true;
    }

 

Set 에 모든 조합 가능한 수를 넣으면서도

 

해당 숫자개수 체크 메소드를 활용해 자기 자신이 포함되었는지 아닌지 여부를 증명해줄 수 있게 되었다.

 

 

 

 

Java 풀이 코드

 

 

import java.util.Set;
import java.util.Iterator;
import java.util.concurrent.CopyOnWriteArraySet;
import java.util.stream.Collectors;

public class Solution {
    // 입력받을 숫자 1의자리수 총 갯수에 대한 배열
    private static int[] countArr = new int[10];
    private static Set<String> set = new CopyOnWriteArraySet<>();

    public static int solution(String numbers) {

        // 자릿수별 숫자개수 할당
        numbers.chars().forEach(v -> countArr[v - 48]++);

        // [입력받은 숫자] 루프
        for (int i = 0; i < numbers.length(); i++) {
            // 루프를 돌며 각각 1자리를 Set에 더해줌
            set.add(numbers.charAt(i) + "");
            Iterator<String> it = set.itertor();
            // Set 의 모든 값들을 돌며
            while (it.hasNext()) {
                // Set에 현재 있는 값들에 [입력받은 숫자] 각각 1자리들을 붙여줌
                pushToSet(it.next(), numbers);
            }
        }
        // String Set => Integer Set
        Set<Integer> intSet = set.stream().map(Integer::parseInt).collect(Collectors.toSet());
        // Integer Set 에서 소수만 찾아서 개수 리턴
        return (int) intSet.stream().filter(v -> isPrimeNumber(v)).count();
    }

    // Set에 숫자를 넣는 메소드
    private static void pushToSet(String currentValue, String numbers) {
        for (int j = 0; j < numbers.length(); j++) {
            if (checkNumLimit(currentValue + numbers.charAt(j), countArr)) {
                // 현재 Set에 존재하는 숫자 앞뒤에 숫자한개를 붙임
                set.add(currentValue + numbers.charAt(j));
                set.add(numbers.charAt(j) + currentValue);
            }
        }
    }

    /**
     * @param n        : 넣을 숫자 문자열
     * @param checkArr : 입력받은 숫자 문자열들 0~9까지의 count 배열
     * @return true    : set에 넣어도 되는 숫자다.
     */
    private static boolean checkNumLimit(String n, int[] checkArr) {
        for (int i = 0; i < n.length(); i++) {
            char c = n.charAt(i);
            if (n.chars().filter(v -> c == v).count() > checkArr[c - 48]) {
                return false;
            }
        }
        return true;
    }

    // 소수 찾는 메소드
    private static boolean isPrimeNumber(int n) {
        if (n <= 1) {
            return false;
        }
        for (int i = 2; i <= (int) Math.sqrt(n); i += 1) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(solution("011"));
    }
}

 

 

자기 자신 문제 때문에 모든 조합가능한 수를 찾지 못해서 틀리던가 너무 많이 조합해서 틀리던가 하며 푸느라 애먹었었는데

 

풀고 다른 사람 풀이를 보니 자기 자신을 제외하고 문자열의 subString 메소드와 재귀를 이용하여 그런 체크 따위 할 필요가 없게 풀었다.

 

 

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);
 }