작성일자 글쓴이 thkmon

[JAVA] 조합(Combination)하는 경우의 수

[JAVA] 조합(Combination)하는 경우의 수

모 기업 코딩테스트를 치른후 순열과 조합에 취약하다는 것을 깨닫고 실습을 위해 코드 작성.

(사실 순열조합 뿐만이 아니라 모든 알고리즘 문제에 취약)

int 배열과 선택 개수를 파라미터로 넘기면 모든 조합(Combination)하는 경우의 수를 가져오는 메서드 getCombination을 작성했다.

(참고로 조합은 순서가 없는 경우의 수. 순열은 순서가 있는 경우의 수)

예를 들어 int 배열은 {1, 2, 3, 4, 5, 6, 6, 5, 4, 3, 2, 1, 4, 3, 2, 6, 5}, 그리고 선택 개수는 4를 넘겼을 때 결과는 아래와 같다.

1. 예제 결과

3,4,5,6
2,4,5,6
2,3,5,6
2,3,4,6
2,3,4,5
1,4,5,6
1,3,5,6
1,3,4,6
1,3,4,5
1,2,5,6
1,2,4,6
1,2,4,5
1,2,3,6
1,2,3,5
1,2,3,4

2. 조합(Combination) 경우의 수를 가져오는 코드

public static void main(String[] args) {
        int[] inputArray = {1, 2, 3, 4, 5, 6, 6, 5, 4, 3, 2, 1, 4, 3, 2, 6, 5};
        ArrayList<int[]> resultList = getCombination(inputArray, 4);
        print(resultList);
    }
    
    
    /**
     * 제네릭이 int 배열인 ArrayList를 출력한다.
     */
    public static void print(ArrayList<int[]> inputList) {
        System.out.println(convertToString(inputList));
    }
    
    
    /**
     * int 배열을 출력한다.
     */
    public static void print(int[] inputArray) {
        System.out.println(convertToString(inputArray, “,”));
    }
    
    
    /**
     * 제네릭이 int 배열인 ArrayList의 내용을 문자열 형태로 만든다.
     */
    public static String convertToString(ArrayList<int[]> inputList) {
        if (inputList == null || inputList.size() == 0) {
            return “”;
        }
        
        StringBuffer buff = new StringBuffer();
        
        int count = inputList.size();
        for (int i=0; i<count; i++) {
            if (buff.length() > 0) {
                buff.append(“\n”);
            }
            
            buff.append(convertToString(inputList.get(i), “,”));
        }
        
        return buff.toString();
    }

    
    /**
     * int 배열의 내용을 문자열 형태로 만든다.
     */
    public static String convertToString(int[] inputArray, String delimiter) {
        if (inputArray == null || inputArray.length == 0) {
            return “”;
        }
        
        StringBuffer buff = new StringBuffer();
        
        int count = inputArray.length;
        for (int i=0; i<count; i++) {
            if (buff.length() > 0) {
                buff.append(delimiter);
            }
            
            buff.append(inputArray[i]);
        }
        
        return buff.toString();
    }

    
    /**
     * 조합 구하기
     */
    public static ArrayList<int[]> getCombination(int[] inputArray, int selectCount) {
        // 미리 중복 제거하고 실행
        inputArray = removeDuplication(inputArray);
                
        ArrayList<int[]> resultList = new ArrayList<int[]>();
        int[] hintArray = new int[inputArray.length];
        
        getSingleCombination(resultList, selectCount, inputArray, 0, hintArray, 0);
        return resultList;
    }
    
    
    /**
     * 조합 구하기 재귀메서드
     */
    public static void addSingleCombination(ArrayList<int[]> resultList, int selectCount, int[] inputArray, int position, int[] hintArray, int hintIndex) {
        
        if (hintIndex == selectCount) {
            int[] singleArray = resizeIntArray(hintArray, hintIndex);
            if (singleArray != null && singleArray.length > 0) {
                resultList.add(singleArray);
            }
            return;
        }
        
        int lastIndex = inputArray.length – 1;
        if (position > lastIndex) {
            return;
        }
        
        int[] hintArray2 = cloneArray(hintArray);
        hintArray[hintIndex] = 0;
        hintArray2[hintIndex] = inputArray[position];
        
        position++;
        
        addSingleCombination(resultList, selectCount, inputArray, position, hintArray, hintIndex);
        addSingleCombination(resultList, selectCount, inputArray, position, hintArray2, hintIndex + 1);
    }
    
    
    /**
     * int 배열을 복제한다.
     */
    public static int[] cloneArray(int[] inputArray) {
        if (inputArray == null) {
            return null;
        }
        
        int count = inputArray.length;
        int[] resultArray = new int[count];
        
        for (int i=0; i<count; i++) {
            resultArray[i] = inputArray[i];
        }
        
        return resultArray;
    }
    
    
    /**
     * int 배열의 길이를 변경한다. (조정한 배열을 새로 얻는다)
     */
    public static int[] resizeIntArray(int[] inputArray, int newSize) {
        int lastIndex = -1;
        if (inputArray != null) {
            lastIndex = inputArray.length – 1;
        }
        
        int[] newArray = new int[newSize];
        
        for (int i=0; i<newSize; i++) {
            if (i > lastIndex) {
                newArray[i] = 0;
            } else {
                newArray[i] = inputArray[i];
            }
        }
        
        return newArray;
    }
    
    
    /**
     * int 배열의 중복을 제거한다.
     */
    public static int[] removeDuplication(int[] inputArray) {
        if (inputArray == null || inputArray.length == 0) {
            return null;
        }
        
        int count = inputArray.length;
        int[] resultArray = new int[count];
        
        int currentIndex = 0;

        int singleItem = 0;
        
        oLoop : for (int i=0; i<count; i++) {
            singleItem = inputArray[i];
            
            for (int k=0; k<resultArray.length; k++) {
                if (resultArray[k] == singleItem) {
                    continue oLoop;
                }
            }
            
            resultArray[currentIndex] = singleItem;
            currentIndex++;
        }
        
        if (currentIndex != count) {
            resultArray = resizeIntArray(resultArray, currentIndex);
        }
        
        return resultArray;
    }