프로그래머스_소수찾기

신창호·2022년 6월 30일

프로그래머스코딩 문제

목록 보기

2/8

문제 구성 📖

코딩테스트 사이트 : 프로그래머스
난이도 : 2단계
풀이 날짜 : 2022.06.29
사용한 풀이 방법 : 완전탐색

문제링크

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

풀이법

소수의 갯수를 구하는 문제이다.
하지만, 한자리 숫가가 적힌 종이조각을 나열하여 만든 숫자에서 소수의 갯수를 파악해야한다.

먼저 주어지는 문자열의 길이가 1~7임으로,
종이조각이 최대 7개라는 것을 알 수 있다.
하지만, 같은 숫자도 나올 수 있음으로, 중복도 생각해야한다.
생각 복잡해질것같아, 필요한 기능을 크게 나눠봤다.

필요한 기능

1개 부터 ~ 최대로 뽑을 수 있는 만큼 종이뽑기
뽑은 수를 기준으로 종이조각 나열하기
나열된 종이조각 숫자로 변경하기
- 단, 중복을 방지해야한다.
변경된 숫자 소수인지 파악하기.

소수가 맞으면, 갯수세기

코드

import java.util.*;
class Solution {
   
   static int count = 0;
   static Set<Integer> set = new HashSet<Integer>();
   public int solution(String numbers) {
    
       
       // 문자열을 하나로 나눈다. 
       String[] numberArray = numbers.split("");
      
       boolean[] visited; 
       
        // 1부터 문자열의 길이 만큼, 선택 순열한다. 
       for(int select = 1; select <= numberArray.length; select++){
       	  // 매번 뽑을 때마다, 초기화
             String[] output = new String[select];
             visited = new boolean[numberArray.length];
           
             DFS(numberArray,output,visited ,0,numberArray.length,select);
       }
      
       return count;
   }
   
   // 순열로 종이 뽑기 
   public void DFS(String[] numArr, String[] output, boolean[] visited, int depth, int n, int r){
       
       if(depth == r) {   // 모두 고르면
           // output의 숫자 확인
           makeNumber(output);
           return;    
       }
       for(int i = 0; i< n; i++){
           if(!visited[i]){
               visited[i] = true;
				output[depth] = numArr[i];
               DFS(numArr, output, visited, depth + 1, n, r);    
				visited[i] = false;
           }
       }
       
   }
   
   // 뽑은 종이 순으로 숫자로 만들기
   public void makeNumber(String[] arr){
       int num = Integer.parseInt(String.join("", arr));
   
       System.out.println(num);
       if(num > 1 && !(set.contains(num))){
           set.add(num);
           if(demicalCheck(num)) {count++;}
              
       }

           
   }
   
   // 소수인지 파악
   public boolean demicalCheck(int num){
       for(int i = 2 ; i <= (num/2); i++){
           if(num % i == 0){return false;}
       } 
       return true;
   }
}

깔끔하게 통과하였지만, 몇가지 리펙토링 할 수 있을것 같다.

현재 보이는 리펙토링

소수인지 파악하는 부분을, 나누기2가 아니라, 제곱근으로 처리하여, 보다 빠른처리가 가능해 보인다.
DFS에서 넘겨주는 인자에 바뀌지 않는 고정값이 보인다. 전역변수로 처리가능해 보인다.

수정된 코드

import java.util.*;
class Solution {
   static String[] numArr; // 전역변수로 전환
   static int n = 0;     // 전역변수로 전환
   static int count = 0;
   static Set<Integer> set = new HashSet<Integer>();
   public int solution(String numbers) {
    
       
       // 문자열을 하나로 나눈다. 
      numArr = numbers.split("");
      n = numArr.length;
       boolean[] visited; 
       
       for(int select = 1; select <= n; select++){
             String[] output = new String[select];
             visited = new boolean[numArr.length];
           
             DFS(output,visited ,0,select);
       }
      
       return count;
   }
   public void DFS(String[] output, boolean[] visited, int depth, int r){ // 파라미터 변환
       
       if(depth == r) {   // 모두 고르면
           // output의 숫자 확인
           makeNumber(output);
           return;    
       }
       for(int i = 0; i< n; i++){
           if(!visited[i]){
               visited[i] = true;
				output[depth] = numArr[i];
               DFS(output, visited, depth + 1, r);    
				visited[i] = false;
           }
       }
       
   }
   public void makeNumber(String[] arr){
       int num = Integer.parseInt(String.join("", arr));
   
       if(num > 1 && !(set.contains(num))){
           set.add(num);
           if(demicalCheck(num)) {count++;}
              
       }

           
   }
   
   
   public boolean demicalCheck(int num){
       for(int i = 2 ; i <= Math.sqrt(num); i++){ // 범위 변환
           if(num % i == 0){return false;}
       } 
       return true;
   }
}