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

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

프로그래머스

 

[풀이과정]

최대 길이 7이므로 1,000,000 -> 최대 수는 9,876,543

0이 맨 앞에 오는 건 의미 없음.

소수 판별 로직

숫자를 조합할 때 같은 숫자가 만들어질 수 있음. boolean[10^n] 이용

 

[내 코드]

class Solution {
       static int length, answer;
    static int[] arr;
    static boolean[] check, numberArr;
    static StringBuilder nowNum;

    public static int solution(String numbers) {
        length = numbers.length();
        //같은 숫자가 만들어졌을 때 판별하기 위해 생성
        numberArr = new boolean[(int)Math.pow(10, length)];
        answer = 0;
        arr = new int[length];
        check = new boolean[length];

        for(int i = 0; i < length; i++){
            //시작 숫자가 0이 아닐 때
            nowNum = new StringBuilder(numbers.substring(i,i + 1));
            if(nowNum.charAt(0) != '0'){
                //체크해주기
                check[i] = true;
                method(numbers);
                check[i] = false;
            }
        }

        return answer;
    }

    public static void method(String numbers){
        int finalNum = Integer.parseInt(nowNum.toString());
        if(!numberArr[finalNum]) {
            numberArr[finalNum] = true;
            //소수판별
            if (isPrime(finalNum)) {
                answer++;
            }
        }

        for(int i = 0; i < length; i++){
            if(!check[i]){
                check[i] = true;
                nowNum.append(numbers.substring(i, i + 1));
                method(numbers);
                check[i] = false;
                nowNum.deleteCharAt(nowNum.length() - 1);
            }
        }
    }

    public static boolean isPrime(int number){
        if(number == 1){
            return false;
        }

        if(number % 2 == 0){
            return number == 2;
        }

        for(int i = 3; i <= Math.sqrt(number); i += 2){
            if(number % i == 0){
                return false;
            }
        }

        return true;
    }
}

 

[다른 사람 풀이]

import java.util.HashSet;
class Solution {
    public int solution(String numbers) {
        HashSet<Integer> set = new HashSet<>();
        permutation("", numbers, set);
        int count = 0;
        while(set.iterator().hasNext()){
            int a = set.iterator().next();
            set.remove(a);
            if(a==2) count++;
            if(a%2!=0 && isPrime(a)){
                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 (n == 0) System.out.println(prefix);
        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);

    }

}

 

[chatGPT]

import java.util.*;

class Solution {
    public int solution(String numbers) {
        Set<Integer> set = new HashSet<>();
        permutation("", numbers, set);
        
        int count = 0;
        for (int num : set) {
            if (isPrime(num)) {
                count++;
            }
        }
        
        return count;
    }

    public boolean isPrime(int n) {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
        
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) return false;
        }
        
        return true;
    }

    public void permutation(String prefix, String str, Set<Integer> set) {
        int n = str.length();
        if (!prefix.isEmpty()) {
            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), set);
        }
    }
}

 

 

[배운 점]

입력 크기가 작고 메모리 사용량을 최소화해야 하는 경우에는 boolean 배열을 사용하는 것이 적합하지만 입력 크기가 크거나 중복을 제거해야 하는 경우에는 Set을 사용하는 것이 더 효율적이라고 한다. 일반적으로는 Set을 사용한다.

 

다른 코드들은 순열메서드로 구할 수 있는 요소를 모두 구해 Set에 넣은 후, 전체를 탐색하며 소수임을 판별하는 방향으로 코드를 구현했다.

 

Integer.parseInt(String str)과 Integer.valueOf(String str)의 차이

1. Integer.parseInt(String str)

• int 반환
• 파싱 불가한 값이 입력되면 예외 발생

언박싱 필요 없음

• 캐싱 사용 안 함

2. Integer.valueOf(String str)

•  Integer 반환
• 파싱 불가한 값이 입력되면 null 반환
• 언박싱 필요
• -128부터 127까지인 경우에는 캐싱을 사용하여 이미 캐시된 객체를 반환합니다. 따라서 이 범위 내의 값은 동일한 객체를 반환합니다. 하지만 범위를 벗어나는 경우에는 매번 새로운 Integer 객체를 생성

public class IntegerCacheExample {
    public static void main(String[] args) {
        // -128부터 127까지의 범위 내에서는 동일한 객체를 반환합니다.
        Integer a = 100;
        Integer b = 100;
        System.out.println("a == b: " + (a == b)); // 출력: true

        // 범위를 벗어나는 경우에는 매번 새로운 객체를 생성합니다.
        Integer c = 200;
        Integer d = 200;
        System.out.println("c == d: " + (c == d)); // 출력: false
    }
}