프로그래머스 - 소수찾기 (sol.java)

◎문제 링크

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

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

---

◎문제 파악

String"12"이 numbers로 들어왔을 때, 각 종이 조각을 붙여 숫자를 만들 수 있으므로, 만들 수 있는 수는 1,2,12,21이다.

이 중에서 소수인 수는 2밖에 없으므로, return 값은 1이다.

 

1. number로 들어온 string을 나누어 숫자 만들기

2. 만들어진 숫자가 소수인지 판별하기

3. 부가적 문제들(ex. 중복되는 요소 처리하기, "011"을 "11"로 다듬기 등)

---

◎1번 sol)

우선 문자열 안에서 이어져 있는 숫자를 하나씩 나누어야 한다.

숫자들을 하나씩 나누어 생각하면, 각 숫자들의 순열(permutation)을 구하는 문제라는 것을 알 수 있다.

 

-for문(중첩 루프)을

String n 크기의 배열이 들어왔을 때, k개를 중복되지 않게 순열로 뽑는 경우의 수 구하기

//n=4, k=2
//4자리 숫자(1234)가 들어왔을때 그중에 중복을 허용하지 않고 2개를 뽑는 순열, 4P2 = 12
String[] people = {"1","2","3","4"};
result(people);


private static void result( String[] people ) {
    int count = 0;
    for( int firstIndex = 0; firstIndex < people.length; firstIndex++ ) {
        for( int secondIndex = 0; secondIndex < people.length; secondIndex++ ) {
            
            if( firstIndex == secondIndex ) continue; //중복 허용X
                
                String first = people[firstIndex];
                String second= people[secondIndex];
                count++;
                System.out.println("( "+first +" " + second + " )");
            }
    }
    System.out.println("총 경우의 수 : " + count);
}

결과:

( 1 2 )
( 1 3 )
( 1 4 )
( 2 1 )
( 2 3 )
( 2 4 )
( 3 1 )
( 3 2 )
( 3 4 )
( 4 1 )
( 4 2 )
( 4 3 )
총경우의 수 : 12

 

for문을 이용하는 것은 k가 커질수록 매우 구현하기 어려워진다.

위의 코드는 k=2이므로, 2개의 for문밖에 쓰지 않았지만, k=4,5,6... 이상이 되면, 4,5,6... 중 for문을 써야 하기 때문에 코드를 작성하기 매우 어려워진다.

 

-재귀를 이용하여 순열 구현하기

String n 크기의 배열이 들어왔을 때, k개를 중복되지 않게 순열로 뽑는 경우의 수 구하기

//n=3, k=3
//3자리 숫자(1233)가 들어왔을때 그중에 중복을 허용하지 않고 3개를 뽑는 순열, 3P3 = 6
String[] people = {"1","2","3"};
result(people);

private static void result( String[] people ) {
    int r = 3;
    boolean[] isChecked = new boolean[people.length]; //boolean은 생성되면 기본적으로 False 값을 가진다
    String[] result = new String[r];
    ArrayList<String[]> totalList = new ArrayList<String[]>(); //만들어진 숫자들을 저장할 ArrayList
    
    //재귀함수
    permutation(people, isChecked, result, r, 0, totalList);
    
    //출력
    for (String[] strings : totalList) {
        String temp = "";
        for( String text : strings ) {
            temp += " " + text;
        }
        System.out.println(temp);
    }
    System.out.println("총 경우의 수 : " + totalList.size());
}

private static void permutation( String[] people, boolean[] isChecked, String[] result, int endPoint, int dept, ArrayList<String[]> totalList ) {
    if( endPoint == dept ) {
        totalList.add(result.clone());
    } else {
        for ( int i = 0; i < people.length; i++ ) {
            if( !isChecked[i] ) {
                isChecked[i] = true; // 사용된 배열 위치
                result[dept] = people[i]; // 저장 
                permutation(people, isChecked, result, endPoint, dept + 1, totalList);
                isChecked[i] = false; // 사용된 것 다시 제자리
                result[dept] = ""; // 저장된 것 제자리
            }
        }
    }
}

※재귀를 이용한 코드는 honbabzone.com/java/java-algorithm-1/의 코드를 가져왔다. 혼자 짜지 못해서..;;

 

결과:

 1 2 3 
 1 3 2
 2 1 3
 2 3 1
 3 1 2
 3 2 1
총경우의 수 : 6

 

우선 결과는 위와 같다.

천천히 코드를 보며 흐름을 따라가자.

 

※재귀 함수 번호에 특별한 의미는 없다. 재귀 함수를 구별하기 위해서 첫번째로 실행된 재귀함수를 (재귀 함수 1)이라고 임의로 정한 것이다.

 

1. 선언된 흐름을 따라가면, isChecked와 result totalList는 아래 표와 같은 값을 가진다.

isChecked	F	F	F
result
totalList

2. permutation(people, isChecked, result, r, 0, totalList);로  (재귀함수 1)으로 들어간다. (dept == 1)

3. endPoint == dept 가 true가 아니고, isChecked[0]이 F이므로, 

                isChecked[i] = true; // 사용된 배열 위치
                result[dept] = people[i]; // 저장 

에 의하여

 

isChecked	T	F	F
result	1
totalList

이 된다.

 

4. permutation(people, isChecked, result, endPoint, dept + 1, totalList);로 (재귀 함수 2)으로 들어간다. (dept == 1)

5. endPoint == dept 가 true가 아니고, isChecked[0]이 T, isChecked[1]이 F이므로,

                isChecked[i] = true; // 사용된 배열 위치
                result[dept] = people[i]; // 저장 

에 의하여

isChecked	T	T	F
result	1	2
totalList

이 된다.

 

6. permutation(people, isChecked, result, endPoint, dept + 1, totalList);로 (재귀함수 3)으로 들어간다. (dept == 2)

7. endPoint == dept 가 true가 아니고, isChecked[0]이 T, isChecked[1]이 T,isChecked[0]이 F이므로,

                isChecked[i] = true; // 사용된 배열 위치
                result[dept] = people[i]; // 저장 

에 의하여

isChecked	T	T	T
result	1	2	3
totalList

이된다.

 

8. permutation(people, isChecked, result, endPoint, dept + 1, totalList);로 (재귀함수 4)으로 들어간다. (dept == 3)

9. endPoint == dept 가 true이므로. result.clone()값이 totalList에 저장된다.

isChecked	T	T	T
result	1	2	3
totalList	(1,2,3)

10. (재귀함수 4)가 종료되었으므로 (재귀함수 3)으로 돌아간다. (dept==2)

                isChecked[i] = false; // 사용된 것 다시 제자리
                result[dept] = ""; // 저장된 것 제자리

에 의해

 

isChecked	T	T	F
result	1	2
totalList	(1,2,3)

이 된다.

 

11. (재귀함수 3)이 종료되었으므로 (재귀함수 2)으로 돌아간다. (dept==1)

                isChecked[i] = false; // 사용된 것 다시 제자리
                result[dept] = ""; // 저장된 것 제자리

에 의해

 

 

isChecked	T	F	F
result	1
totalList	(1,2,3)

12. (재귀함수 2)의 남은 for문을 실행한다. isChecked[1]이 F이므로,

                isChecked[i] = true; // 사용된 배열 위치
                result[dept] = people[i]; // 저장 

에 의해,

 

isChecked	T	F	T
result	1	3
totalList	(1,2,3)

이 된다.

 

13. permutation(people, isChecked, result, endPoint, dept + 1, totalList);로 (재귀함수 5)으로 들어간다. (dept == 2)

14. endPoint == dept 가 true가 아니고, isChecked[0]이 T, isChecked[1]이 F이므로,

                isChecked[i] = true; // 사용된 배열 위치
                result[dept] = people[i]; // 저장 

에 의하여

isChecked	T	T	T
result	1	3	2
totalList	(1,2,3)

이 된다.

 

15. permutation(people, isChecked, result, endPoint, dept + 1, totalList);로 (재귀함수 6)으로 들어간다. (dept == 3)

16. endPoint == dept 가 true이므로. result.clone()값이 totalList에 저장된다.

 

isChecked	T	T	T
result	1	3	2
totalList	(1,2,3),(1,3,2)

17. (재귀함수 6)이 종료되었으므로 (재귀함수 5)으로 돌아간다. (dept==2)

                isChecked[i] = false; // 사용된 것 다시 제자리
                result[dept] = ""; // 저장된 것 제자리

에 의해

isChecked	T	F	T
result	1		2
totalList	(1,2,3),(1,3,2)

이 된다.

18. (재귀함수 5)의 남은 for문을 실행한다. isChecked[3]이 T이므로, (재귀함수 5)가

종료되고, (재귀함수 2)로 돌아간다. (dept==1)

                isChecked[i] = false; // 사용된 것 다시 제자리
                result[dept] = ""; // 저장된 것 제자리

에 의해

isChecked	T	F	F
result	1
totalList	(1,2,3),(1,3,2)

이 된다.

 

19. (재귀함수 2)가 종료되고, (재귀함수 1)로 돌아간다. (dept==0)

                isChecked[i] = false; // 사용된 것 다시 제자리
                result[dept] = ""; // 저장된 것 제자리

에 의해

isChecked	F	F	F
result
totalList	(1,2,3),(1,3,2)

이된다.

 

이러한 과정을 계속해서 거치면,  

(1 2 3)(1 3 2)(2 1 3)(2 3 1)(3 1 2)(3 2 1)
총경우의 수 : 6의 결과가 나오게 된다.

 

---

◎2번 sol)

숫자 n이

            if(tmper==1 || tmper==0){} // 숫자 n이 0,1이면 그냥 넘어가고
            else if(tmper==2){ //2이면 숫자라고 판단
                answer++;
            }else{ //2이상의 숫자일경우
            //n을 2~n-1까지의 숫자로 나눈 나머지가 모두 0이 아니어야한다.
                int p = 0;
                for(int i = 2; i<tmper; i++){
                    if(tmper%i==0){
                      p++;
                    }
                }
                if(p==0){
                    answer++;
                }
            }

 

◎3번 sol)

주어진 number 가 만약 "110"이라면 순열 재귀 함수는 {0,1,1,11,11,10,10,01,01,110,110,101,101,011,011}의 숫자들을 만들게 되고, 이는 숫자들이 중복되는 문제, 011과 같이 0이 앞으로 오는 문제가 발생한다.

 

-중복되는 요소 처리하기

중복을 알아서 처리해주는 HashSet class를 사용해서 중복되는 class를 처리하였다.

HashSet이란?

kkwong-guin.tistory.com/39

Java - HashSet 클래스

-0이 앞으로 오는 문제 처리하기

문자열의 처음부터 어디까지 0으로 이루어져 있는지 알아내서, 그만큼 문자열을 잘라낸다.

        for(String tempt : totalList){
            int i = 0;
            while(i<tempt.length() && tempt.charAt(i)=='0'){ //어디까지 0인지 알아낸다
                i++;
            }
            if(i>0){
                set.add(Integer.parseInt(tempt.substring(i-1))); 
                //0이 있으면, 잘라서 Hashset에 추가
            }else{
                set.add(Integer.parseInt(tempt));
                //0이 없으면, 그냥 Hashset에 추가
            }
        }

전체 코드:

import java.util.*;

class Solution {
    
    private static ArrayList<String> result( char[] people ) {
        int r; //r개의 숫자 정렬
        boolean[] isChecked = new boolean[people.length];
        ArrayList<String> totalList = new ArrayList<String>();
        
        //for 문을 돌려 r의 값을 바꿈으로서, 순열들의 합(==만들수 있는 모든수)을 찾는다.
        //ex) "12"로 만들수 있는 수의 개수 = 2p1 + 2p2 (순열들의 합) = 4
        for(r = 1; r<=people.length; r++){ 
            String[] result = new String[r];
            permutation(people, isChecked, result, r, 0, totalList);
        }
        
        return totalList;
    }

    private static void permutation( char[] people, boolean[] isChecked, String[] result, int endPoint, int dept, ArrayList<String> totalList ) {
        if( endPoint == dept ) {
            String tmp="";
            for(int i = 0; i<result.clone().length; i++){
                tmp = tmp + result.clone()[i];
            }
            totalList.add(tmp);
        } else {
            for ( int i = 0; i < people.length; i++ ) {
                if( !isChecked[i] ) {
                    isChecked[i] = true; // 사용된 배열 위치
                    result[dept] = Character.toString(people[i]); // 저장 
                    permutation(people, isChecked, result, endPoint, dept + 1, totalList);
                    isChecked[i] = false; // 사용된 것 다시 제자리
                    result[dept] = ""; // 저장된 것 제자리
                }
            }
        }
    }
    
    public int solution(String numbers) {
        int answer = 0;
        
        char tmp[] = numbers.toCharArray(); //String 문자열을 한개씩 쪼개서 char 배열로 만든다
        ArrayList<String> totalList = result(tmp); //순열로 만드는 함수에 넣는다
        HashSet<Integer> set = new HashSet<Integer>();
        for(String tempt : totalList){
            int i = 0;
            while(i<tempt.length() && tempt.charAt(i)=='0'){ //어디까지 0인지 알아낸다
                i++;
            }
            if(i>0){
                set.add(Integer.parseInt(tempt.substring(i-1)));
                //0이 있으면, 잘라서 Hashset에 추가
            }else{
                set.add(Integer.parseInt(tempt));
                //0이 없으면, 그냥 Hashset에 추가
            }
        }
        
        Iterator iter = set.iterator();	// Iterator 사용
        while(iter.hasNext()) {//값이 있으면 true 없으면 false
            
            int tmper= (int)iter.next();
            if(tmper==1 || tmper==0){} // 숫자 n이 0,1이면 그냥 넘어가고
            else if(tmper==2){//2이면 숫자라고 판단
                answer++;
            }else{//2이상의 숫자일경우
            //n을 2~n-1까지의 숫자로 나눈 나머지가 모두 0이 아니어야한다.
                int p = 0;
                for(int i = 2; i<tmper; i++){
                    if(tmper%i==0){
                      p++;
                    }
                }
                if(p==0){
                    answer++;
                }
            }
            
        }
        
        return answer;
    }   
}

---

◎다른 사람의 풀이

import java.util.HashSet;
class Solution {
    public int solution(String numbers) {
        HashSet<Integer> set = new HashSet<>(); //HashSet 사용
        permutation("", numbers, set);
        int count = 0;
        while(set.iterator().hasNext()){
            int a = set.iterator().next();
            set.remove(a);
            if(a==2) count++;
            if(a%2!=0 && isPrime(a)){
                count++;
            }
        }        
        return count;
    }

    public boolean isPrime(int n){
        if(n==0 || n==1) return false;
        for(int i=3; i<=(int)Math.sqrt(n); i+=2){
            if(n%i==0) return false;
        }
        return true;
    }

        public void permutation(String prefix, String str, HashSet<Integer> set) {
        int n = str.length();
        if(!prefix.equals("")) set.add(Integer.valueOf(prefix));
        for (int i = 0; i < n; i++)
          permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);

    }

}

---

◎코드 개선 & 추가 학습:

인터넷을 찾아보니 소수 구하는 알고리즘이

"소수는 1과 N만을 약수로 가진다. 그럼 2부터 N-1까지의 수로는 나눠져서는 안 된다."보다

더 발전된 알고리즘이 있었다.

 

kkwong-guin.tistory.com/41

Java - 소수 찾기

 

순열(permutation) 뿐만 아니라 조합(combination)도 재귀 함수로 우아하게 구현할 수 있다.

 

kkwong-guin.tistory.com/43

Java - 순열 조합 알고리즘