프로그래머스_소수찾기

신창호·2022년 6월 30일
0
post-thumbnail

문제 구성 📖

코딩테스트 사이트 : 프로그래머스
난이도 : 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;
       }
    }

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

현재 보이는 리펙토링

  1. 소수인지 파악하는 부분을, 나누기2가 아니라, 제곱근으로 처리하여, 보다 빠른처리가 가능해 보인다.
  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;
       }
    }

다른 사람과 비교하기

문자열을 문자배열로 바꾸지않고, 문자열 그자체로 순열을 돌리신 분의 풀이를 보았다.

다른점

  • 문자열을 굳이 문자열배열로 만들지않고, 문자열(String)그 자체로 풀었다.
  • HashSet<>에 값을 넣고, set의 길이로 소수의 갯수를 파악
  • 방문배열을 따로 만들지않고 다음 재귀할때, 사용했던 문자열을 제외한 문자열을 만들어 재귀를 돌림.(이게 미쳤음..)

참고한 점

  • 소수를 찾는 부분을 3부터 시작하여, 연산횟수를 줄인 작업이 인상 깊었다.

하지만 아쉽게도, 문자열 연산부분에서 오래걸리기 때문에 속도면에서는 빠르게 처리못함.
그래서 참고는 하되, 효율적인 코드인가 했을때, 의문이 든다.

profile
한단계씩 올라가는 개발자

0개의 댓글