[프로그래머스] JAVA LV2 "소수 찾기" 풀이 방법 / set 자료구조 사용

자바 문법 정도만 레퍼런스를 받고, 알고리즘 자체는 직접 구현한 풀이 방법이다.

set을 활용한 부분에 있어서는 다른 사람들의 코드를 살펴보니 대부분 사용하는 편인 것 같았다.

 

전체적인 진행 방향은 다음과 같다.

1. 문자열에 들어 있는 0~9 숫자들을 INT 타입으로 바꾸어 int배열에 저장한다.
2. 배열에 저장된 수를 가지고, 직접 짠 조합 알고리즘을 통해 가능한 모든 숫자 조합을 찾아 SET 자료구조에 저장한다.
3. SET에 저장된 숫자가 소수인지 판별하여, 소수인 경우에만 카운트를 한다.

 

SET 자료구조

- 중복된 값을 저장하지 않아서 유니크한 값으로만 구성된다.
- Set 자료구조는 인터페이스라서 HashSet로 Integer를 명시해서 생성해야 한다.

• 문자열에 들어있는 숫자를 조합해 나올 수 있는 모든 수를 구해야 한다.
• permutation 함수를 이용할 수 있었는데, 존재를 까먹고 조합 알고리즘을 직접 구현함.
• 문자열의 각 숫자를 INT 형식으로 바꾸어 INT타입의 배열에 저장해줌.
• 그 INT배열을 가지고 숫자를 조합하는데, 중복된 숫자 값이 생성될 수 있으므로 Set 자료구조를 사용해서 중복된 값이 들어가지 않도록 하였음.
• 일단, 자리수 하나의 숫자들을 set에 저장.
• 그리고 각각의 저장된 숫자를 제외한 배열 값을 갖는 새로운 배열을 만들어서 재귀적으로 가능한 조합을 만들 수 있도록 하는 함수의 인자로 넣어줌.
• 그 함수가 makePrime인데, 함수이름만 makePrime이고, 사실상 조합을 만드는 함수임. 나의 실수.
• makePrime함수에서는 주어진 배열과, set, 이전에 이미 방문?했던 앞자리 수를 인자로 받음.
• 그리고 앞자리수가 하나 제외되어있는 주어진 배열에 있는 값을 하나씩 앞자리 수에 더하여 수를 만들고 set에 집어 넣음.
• 이때 앞자리 수에 10을 곱하고 배열에 있는 값 중 현재 가리키는 값을 더함으로써 새로운 수를 만들 수 있음.
• 그리고 makePrime함수를 재귀호출함으로써 위의 과정을 반복하다 보면, set에는 모든 가능한 숫자 조합이 만들어져 있음.
• 이 set을 가지고, 순회하면서, 만약 값이 0,1이라면 소수로 포함하지 않고, 2,3,5,7이라면 소수로 카운팅 함.
• 그리고 2의 배수라면 소수로 포함하지 않고, 2의 배수가 아니라면 해당 값을 3부터 (해당값/3)을 한 값까지로 나누었을 때 나머지가 0이면 => 1과 자기 자신 말고도 나눠지는 값이 있다는 것이므로 소수가 아니고, 카운팅 하지 않는다. 만약 그런 값이 하나도 없었다면(=>불리언 값으로 판단함) 소수로 카운팅한다.
• 위의 과정을 거침으로써 소수의 개수를 찾을 수 있다.
• 다소 복잡하게 보이지만, 스스로 짰다는 것에 의의를 둔다.
• 메소드를 익히는 것도 중요해 보인다.

 

전체 코드이다.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] removeValue(int[] arr, int remove){
        int[] newarr = new int[arr.length-1];
        int first = 0;
        int index = 0;
        for(int i : arr){
            if(i==remove && first==0){
                first = 1;
            }else{
                newarr[index]=i;
                index++;
            }
        }
        
        return newarr;
    }
    
    public void makePrime(int[] arr, Set<Integer> set, int prev){
        for(int i=0; i<arr.length; i++){
            set.add(prev*10+arr[i]);
            int[] newarr = removeValue(arr, arr[i]);
            makePrime(newarr, set, prev*10+arr[i]);
        }
    }
    
    public int solution(String numbers) {
        int answer = 0;//count
        
        int[] nums = new int[numbers.length()];
        Set<Integer> set = new HashSet<>();
        
        for(int i=0; i<numbers.length(); i++){
            nums[i] = Character.getNumericValue(numbers.charAt(i));
        }
        
        for(int i=0; i<nums.length; i++){
            set.add(nums[i]);
            int[] newarr = removeValue(nums, nums[i]);
            makePrime(newarr, set, nums[i]);
        }
        
        //set에는 가능한 모든 값들이 생성된다.
        
        for(int i : set){
            if(i==0 || i==1){//0이거나 1이면 패스
                continue;
            }
            if(i==2 || i==3 || i==5 || i==7){//2,3,5,7이면 count
                answer++;
                continue;
            }
            if(i%2==0){//2의 배수이므로 패스
                continue;
            }else{
                int isPrime = 1;
                for(int j=3; j<=(i/3); j++){
                    if(i%j==0){
                        isPrime=0;
                        break;
                    }
                }
                if(isPrime==1) answer++;
            }
        }
        
        return answer;
    }
}

 

 

이 문제를 푸는데만 1시간 반이 걸렸지만, 성공한게 뿌듯했다.