완전탐색 - 순열

1.  개요

n개의 숫자로 가능한 모든 순열을 만드는 문제입니다.

2. 고난과 역경

완전탐색이 그렇게 어려운 문제는 아니라고 하는데 저한테는 왜 이렇게 골치가 아팠는지 모르겠습니다.

1) 잦은 실수

소수를 찾기 위해 n 보다 작은 수 (i < n) 로 모조리 나눠보던 기존의 코드에서,

효율성을 높여보겠다고 n의 제곱근* 까지 (i < Math.sqrt((double)n) 로 범위를 좁힌 게 화근이었습니다.

간단하게 더하기 1을 해주니 i < Math.sqrt((double)n) + 1  제곱근 값이 포함되면서 해결되었습니다.

이외에도 순열이 0으로 시작하는 경우의 문제라든지 문자열을 붙이는 순서 같은 것들이 여러 번 발목을 잡는 통에 시간을 지체하게 되었습니다.

완전탐색의 경우 적당히 어림잡아서 때려맞히는 것이 불가능하다보니 값을 하나라도 놓치거나 뭔가 조금만 틀어져도 실패하게 되는 것 같습니다.

* 소수는 1과 자기 자신만을 약수로 갖는 수 입니다.

22의 약수는 1 2 11 22 와 같이 대칭을 이룹니다.

9의 경우 1 3 9 로, 제곱근 이하의 값으로만 나눠 봐도 이 수의 약수가 얼마나 존재하는지 알 수 있습니다.

2) 적절한 로직을 구성하는 것이 느림

이런 문제는 공간이나 시간을 적당히 희생시켜야 하는 문제라고 생각됩니다.

적절한 자료구조를 찾아서 모든 값을 다 때려넣고 원하는 값만 뽑아내거나

중복이 되든 말든 재귀함수를 끊임없이 돌려서 필요한 결과를 얻는 식으로요.

그동안 코딩테스트에서 이러한 유형의 문제를 만나면 시간 내에 끝내는 일이 드물었습니다. 해결방법이 좀처럼 떠오르질 않더군요.

아마 java를 손발처럼 능수능란하게 다루질 못해서 그런가봅니다.

오랜 고민의 시간과 컨닝을 통해서 제가 택한 방법은

숫자 하나를 고르면, 문자열에 자기 숫자를 이어붙인 뒤 다음 숫자를 고르는 함수를 호출하는 것입니다.

가령 1, 2, 3 으로 순열을 만든다고 하면

lv.1 에서 pick(1) 은 1 을 완성시키고 다시 pick(2)와 pick(3)을 호출합니다.

lv.2 의 pick(2)는 1에다 2를 이어붙여 12를 완성 후 pick(3)을 호출합니다.

lv.3 의 pick(3)은 12에 3을 붙이고 123을 완성시킵니다.

이렇게 하면 1, 12, 123 세 가지 순열을 얻을 수 있습니다. 마찬가지로 1, 13, 132 를 얻을 수 있고 2와 3에 대해서 반복하면 전체 순열을 구할 수 있습니다.

이를 위해서 이미 고른 숫자를 저장할 picked 배열과 이미 완성된 순열을 저장할 numset Set

그리고 이전 함수에서 완성한 숫자를 저장할 문자열 prev 가 필요했습니다.

 

3. 구현

 

import java.util.*;

class Solution {
    public int solution(String numbers) {
        int answer = 0;
        int[] picked = new int[numbers.length()]; 
       	Set<String> numset = new HashSet<String>();
       	String prev = "";
       	
        //numbers의 i번째 숫자에 대해 카드뽑기를 시작합니다.
        for(int i = 0; i < numbers.length(); i++) {
        	Arrays.fill(picked, 0);
        	prev="";
        	answer+=pick(numset, picked, numbers, prev, i, 1);
        }
        
        System.out.println(numset);
        return answer;
    }
    
    public static int pick(Set<String> nset, int[] picked, String nums, String prev, int n, int lv) {
    	//효율성을 위해 첫번째 카드가 0인 때에는 종료
    	if(lv==1&&nums.charAt(n)=='0') return 0;
    	
    	int ret = 0;
    	// 뽑은 카드를 문자열 뒤에 붙입니다.
    	picked[n] = 1;
    	prev += Character.toString(nums.charAt(n));
    	
        // 다음카드를 뽑습니다.
    	for(int i = 0; i < nums.length(); i++) {
    		if(picked[i]!=1) {
    			ret+=pick(nset, picked, nums, prev, i, lv+1);
    			picked[i]=0;  
    		}   		
    	}
    	// 중복이 아니고 소수이며 0으로 시작하지 않을 경우 반환값에 1을 더해줍니다.
    	if(nset.add(prev)&&isPrime(Integer.parseInt(prev))&&prev.charAt(0)!='0') ret++;
    	return ret;
    }
    
    //소수인지
    public static boolean isPrime(int n) {
        if(n==2) return true;
        else if(n==1||n==0) return false;
        else {
            int i = 2;
            while(i < Math.sqrt((double)n)+1) { 
            	if(n%i == 0) return false;
            	i++;
            }
        }
        return true;
    }
    
}

 

4. 반성

다른 사람들의 풀이를 보니, 굳이 파라미터를 6개나 사용하지 않았어도 더 간단히 구현이 가능했음을 깨닫고 참회의 시간을 가지게 되었습니다.

pick()에 전체 문자열을 계속 줄 것이 아니라,

자기 것만 빼고 다음 사람에게 건내주면 되는 것이었습니다.

pick(1) 은 pick(2)에게 "1"과 "23"을 건내어주고 pick(2)는 pick(3) 에게 "12"와 "3"을 건내어주면

굳이 picked로 사용된 숫자를 일일이 확인, 기록할 필요도 없고 lv이나 n도 필요가 없는 것이었습니다...

 

 

관련문제: 프로그래머스 코딩 테스트 연습 소수찾기, https://programmers.co.kr/learn/challenges