TIL (2022.02.14)

➕ 오늘 푼 문제

프로그래머스 - 소수 찾기

➕ 아이디어

• 최대 범위 (1000000 미만)까지의 소수 목록을 구한다 (→ 아리스토테네스의 체)
  • 아니면 numbers의 길이 만큼 소수 목록을 구해도 된다.
• numbers로 만들 수 있는 숫자 목록을 구한다. (순열)
  • ⭐ 순열 구현 방법
    1. 현재까지 고른 숫자들을 집합(set)에 추가한다.
    2. 반복문을 돌면사 남은 숫자 중 하나의 숫자를 골라 추가한다.
       1. 남은 숫자가 없다면 반복문을 더 돌지 않는다. 이게 재귀가 끝나는 조건이다.
    3. 2번에서 고른 숫자들과 남은 숫자들을 가지고 재귀문을 통해 구한다.
  • 해당 목록 중에 소수가 있다면 answer 수를 증가한다.

➕ Java 코드

import java.util.*;

class Solution {
    public boolean[] getPrimes(int maxSize){
        boolean[] isPrime = new boolean[maxSize];
        Arrays.fill(isPrime, true);
        
        isPrime[0] = false;
        isPrime[1] = false;
        
        for(int i=2; i<maxSize; i++){
            if(isPrime[i]){
                for(int j=2; j<maxSize/i; j++){
                    isPrime[i*j] = false;
                }
            }
        }
        return isPrime;
    }
    
    public void permutations(String prefix, String left, HashSet<Integer> set){
        int n = left.length();
        
        if(!prefix.isEmpty()){
						// 아직 아무것도 선택되지 않은 게 아니라면 선택한 숫자들을 하나의 수로 만들어서 집합에 넣는다.
            set.add(Integer.parseInt(prefix));
        }
        
        for(int i=0; i<n; i++){
						// 아직 뽑지 않은 숫자들 중 하나씩 뽑아 재귀적으로 호출한다.
            permutations(prefix + left.charAt(i), left.substring(0, i) + left.substring(i+1, n), set);
        }
        
    }
    
    public int solution(String numbers) {
        int answer = 0;
        int maxSize = (int) Math.pow(10, numbers.length()+1);
        boolean[] isPrime = getPrimes(maxSize);
        
				// 만들 수 있는 숫자 집합을 구한다.
        HashSet<Integer> set = new HashSet<Integer>();
        permutations("", numbers, set);
        
        for(int i : set){
            if(isPrime[i]){
                answer += 1;
            }
        }
        
        
        return answer;
    }
}

➕ Python 코드

from itertools import permutations

def getPrimes():
		# 아리스토테네스의 체로 소수 목록 구함
    MAX_NUM = 10000000
    isPrime = [True] * MAX_NUM
    
    isPrime[0] = False
    isPrime[1] = False
    
    for i in range(2, MAX_NUM):
        if isPrime[i]:
            for j in range(2, MAX_NUM//i):
                isPrime[i*j] = False
                
    return isPrime     
    
def solution(numbers):
    answer = 0
    isPrime = getPrimes()
    
    candidates = []
    for length in range(1, len(numbers)+1):
        candidates += list(map(''.join, permutations(numbers, length)));
    
		# 중복되지 않는 숫자 목록 생성
    candidates = set(map(int, candidates))
    
    for n in candidates:
        if isPrime[int(n)]:
						# 소수라면 카운트 증가
            answer += 1
    
    return answer

➕ 궁금한 내용 및 소감

• 주어진 숫자를 가지고 만들 수 있는 숫자 목록을 구해야 했기 때문에, 순열이 필수적으로 필요했다. 파이썬의 경우 내장함수로 순열과 조합을 쉽게 구현할 수 있는데, 자바는 직접 구현해야 해서 조금 골치가 아프다. 그래서 이 부분은 다른 분의 좋은 코드를 참고하였다. 자바에서 순열과 조합을 구현하는 방법에 대해 공부하고 체득할 필요가 있다고 느꼈다!

➕ 참고 문헌

• Java - boolean 형 배열 초기화
  • Arrays.fill() 함수를 통해 배열 초기화를 할 수 있다.
  • 참고 링크: [JAVA] Boolean형 배열 초기화
• Java - 집합
  • 보통은 HashSet을 이용해 많이 구현한다.
  • 참고 링크: Java HashSet 합집합, 차집합, 교집합, 부분집합
• Java - 문자열 자르기
  • str.substring(strart, end) 를 통해 문자열을 자를 수 있다.
  • 참고 링크: [Java] 문자열 자르기(Substring, Split) 사용법 & 예제
• Java - 제곱 수 구하기
  • Math.pow(base, exponent)를 통해 제곱 수(base^exponent)를 구할 수 있다.
  • 참고 링크: [Java] 자바 거듭 제곱 구하기 Math.pow()