[코테/JAVA] 완전탐색 : 소수 찾기

2022.02.27

84번째 포스팅

 

입사 357일차.

코테 문제풀이 14주차 1번 문제

 

 

0. 문제

  ① 완전탐색 : 소수 찾기

  ② 설명

문제설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

  ③ 링크

코딩테스트 연습 - 소수 찾기

 

 

1. 접근방법

  생각해낸 방법은 1가지

  ① 백트래킹(완전탐색)

 

 

2. 풀이

  ① 접근방법 : ①

  ② 풀이

import java.util.*;
 
class Solution {
    /*
     * 시작시간: 21:00
     * 종료시간: 22:02
     */
    
    /*
     * 0. 전역변수선언
     * 중복숫자판별을 위한 HashSet makedNumberSet
     * 소수의 갯수를 저장하는 int result 
     */
    public static Set<Integer> makedNumberSet = new HashSet<>();
    public static int result = 0;
    
    
    public int solution(String numbers) {
        dfs("", numbers);
        int answer = result;
        return result;
    }
    
    /*
     * 메소드명: dfs
     * 조합이 될 수 있는 숫자를 완전탐색
     */
    public void dfs(String makedNumber, String numbers) {
        
        if (!"".equals(makedNumber)) {
            int chckNum = Integer.parseInt(makedNumber);
            
            /*
             * HashSet.contains() 메소드를 이용해서 중복된 숫자가 있는지 체크
             * 중복된 숫자가 없는 경우 소수판별 메소드 호출
             */
            if (!makedNumberSet.contains(chckNum)) {
                makedNumberSet.add(chckNum);
                if (chckPrimeNumber(chckNum)) {
                    result++;
                }
            }
        }
        
        /*
         * 재귀시작
         * 예시) 123
         * makedNumber = 1 / numbers = 23
         * makedNumber = 12 / numbers = 3
         * makedNumber = 123 / numbers = '' (depth - 1)
         * makedNumber = 13 / numbers = 2
         * ...
         */
        for (int i = 0; i < numbers.length(); i++) {
            dfs(makedNumber + numbers.charAt(i), numbers.substring(0, i) + numbers.substring(i + 1));
        }
        return;
    }
    
    /*
     * 메소드명: chckPrimeNumber
     * 소수판별
     */
    public boolean chckPrimeNumber(int number) {
        if (number < 2) {
            return false;
        }
        int sqrtNum = (int)Math.sqrt(number);
        for (int i = 2; i <= sqrtNum; i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

 

3. 결과

 

 

4. 소감

  - 백트래킹을 처음 구현해봤다. (이론 및 예시코드)    이전에 구현한 dfs와 달리 for문을 사용해서 depth 파라미터를 사용하지 않고 완전탐색이 되도록 만드는 것이 어려웠다.    depth 파라미터를 추가해서 if문으로 재귀탈출문을 구현하는 것이 선호되는 이유를 알 것 같다.