프로그래머스 - 소수찾기(완전탐색, 에라토네스의 체)

programmers.co.kr/learn/courses/30/lessons/42839#qna

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

요즘 코딩테스트 시즌이라 알고리즘 관련된 포스팅만 올리는 것 같습니다.

이 문제는 소수찾기 문제인데 이걸 백트래킹으로 풀어야할지 아니면 다른 방식으로 풀어야할지 많이 고민하다가 방법을 찾은것 같아서 그 방식대로 풀어봤는데 자바로 문자열 다루는게 쉽지 않았고 특히 deep copy때문에 고생했습니다...

문제

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbersreturn

17	3
011	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

문제 풀이 방법

일단 소수를 찾는 문제이기때문에 첫 번째로 에라토네스의 체가 떠올랐습니다.. 이전 글에서 포스팅하면서도 이걸 쓸까? 긴가민가 했는데 이걸 쓸 줄이야.. 그 다음에는 에라토네스의 체를 어떻게 활용해야되지? 라는 생각이 바로 들었어요.

첫 번째로 한 생각은 에라토네스의 체로 소수를 판별한 배열을 만들자

두 번째로는 소수이면 이걸 숫자카드로 만들 수 있는지 판별하자!

풀이 방법은 명확해졌는데 이걸 코드로 구현하려니까.. 어려웠습니다.. 왜냐하면 자바의 객체를 복사한다는게 갑자기 머리가 아프더라고요 이거 완전 기촌데..

그럼 에라토네스의 체로 만들기 위해서는 문자열을 정렬해서 가장 큰숫자로 만드는 과정을 사전에 시행한 후에 에라토네스의 체로 소수를 판별한 배열을 만듭니다.

두 번째는 이제 소수 판별한 배열을 돌면서 소수를 리스트에 담습니다.

마지막으로 리스트의 반복문을 돌면서 숫자카드로 만들 수 있는지 판단하면 끝!

숫자카드로 만들 수 있는지 판별하는 방법은 소수의 수가 숫자카드 안에 포함되어 있는지 판단하고 포함되어 있다면 숫자카드 하나를 제거하면 됩니다!

아 적으면서 드는 생각이 리스트에 담아서 하나씩 지울걸.. ㅜㅜㅜㅜ이라는 생각이..............

코드도 상당히 긴데 코드를 함축할 수 있는 방법 몇개가 떠오르네여.. 더 열심히 공부해야겠습니다 ㅎㅎ

풀이

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class 소수찾기1 {

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution("11");
    }

    static class Solution {

        public int solution(String numbers) {
            int answer = 0;

            int[] arr = changeIntArr(numbers);
            Arrays.sort(arr);
            arr = descArr(arr);
            int max = getMaxInt(arr);
            ArrayList<Integer> arrayList = getSosuArr(max);

            for(int i=0; i<arrayList.size(); i++){
                String cur = String.valueOf(arrayList.get(i));
                String copy = String.copyValueOf(numbers.toCharArray());
//                System.out.println("CUR " + cur + "COPY " + copy);
                boolean flag = true;
                int cnt = 0;
                for(int k=0; k<cur.length(); k++){
                    for(int j=0; j<copy.length(); j++){
                        if(cur.charAt(k) == copy.charAt(j)){
                            copy = copy.replaceFirst(String.valueOf(cur.charAt(k)),"");
//                            System.out.println("CUR " + cur + "COPY " + copy);
                            cnt++;
                            break;
                        }
                    }
                }
                if(cnt == cur.length())
                    answer++;
            }

            System.out.println(answer);
            return answer;
        }


        public ArrayList<Integer> getSosuArr(int max){
            int[] sosu = new int[max+1];
            ArrayList arrayList = new ArrayList();
            for(int i=2; i<= max; i++){
                sosu[i] = i;
            }
            for(int i=2; i<=max; i++){
                if(sosu[i] == 0) continue;
                for(int j=i+i; j<=max; j += i){
                    sosu[j] = 0;
                }
            }

            for(int i=2; i<=max; i++){
                if(sosu[i] != 0) {
                    arrayList.add(sosu[i]);
                }
            }

            return arrayList;
        }

        public int getMaxInt(int[] arr){
            StringBuilder stringBuilder = new StringBuilder();
            for(int i=0; i<arr.length; i++){
                stringBuilder.append(arr[i]);
            }
            return Integer.parseInt(stringBuilder.toString());
        }

        public int[] descArr(int[] arr){
            int[] arr2 = new int[arr.length];
            for(int i=0; i<arr.length; i++){
                arr2[arr.length-i-1] = arr[i];
            }
            return arr2;
        }

        // 숫자배열로 변환
        public int[] changeIntArr(String numbers){
            int[] arr = new int[numbers.length()];
            for(int i=0; i<numbers.length(); i++){
                arr[i]  = Integer.parseInt(String.valueOf(numbers.charAt(i)));
            }
            return arr;
        }
    }


}