[프로그래머스] 후보키 Java 조합 - 재귀 , 백트래킹

 

파이썬을 이용한 코딩테스트시 간단하게 라이브러리를 호출하여 조합을 뽑아내는 것 이 가능했지만 자바는 직접구현을 해야한다.

 

숫자 4가 주어졌을때 

1 , 2, 3,4 , (1,2),(1,3) ,,,, (1,2,3,4) 와 같은 숫자를 출력하는 코드를 짜보자.

 

n = 4 일때  , nCr 을 구현하니 변수 r 도 필요하다.

 

재귀를 사용하며 , 배열의 크기와 r 이 같으면 탈출 하는 조건문을 추가해준다.

 

@Test
    public void combination_test() {
        int n = 4;
        var s = showCombination(n);
        System.out.println(s);
    }
    List<Set<Integer>> answer = new ArrayList<>();
    public int showCombination(int n) {
        for(int r = 1 ; r <= n ;r++){
            generateCombination(n,r);
        }
        return n ;
    }
    public void generateCombination(int n ,int r) {
        List<Integer> combination = new ArrayList<>();
        generate(n,r,1,combination);
    }
    public void generate(int n ,int r ,int start , List<Integer> combiantion){
        if(combiantion.size() ==r){
            System.out.println(combiantion);
            return;
        }
        for(int i = start ; i <= n ; i++){
            combiantion.add(i);
            generate(n,r,i+1,combiantion);
            combiantion.remove(combiantion.size() -1);
        }
    }

출력은 다음과 같다.

 

[1]
[2]
[3]
[4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]
[1, 2, 3, 4]

 

 

@Test
    public void combination_less_method_test() {
        int n = 4 ;
        List<List<Integer>> combinations = new ArrayList<>();
        combine(n,1,new ArrayList<>(),combinations);
        for(List<Integer> combination : combinations){
            System.out.println(combination);
        }
    }
    public void combine(int n , int start  , List<Integer> current , List<List<Integer>> combinations) {
        if(!current.isEmpty()) {
            combinations.add(new ArrayList<>(current));
        }
        for(int i = start ; i <= n; i++) {
            current.add(i);
            combine(n,i+1,current,combinations);
            current.remove(current.size() -1);
        }
    }

 

[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 4]
[1, 3]
[1, 3, 4]
[1, 4]
[2]
[2, 3]
[2, 3, 4]
[2, 4]
[3]
[3, 4]
[4]

 

 

위의 개념을 적용할 문제는 다음과 같다.

 

프로그래머스 후보키 문제이다.

https://school.programmers.co.kr/learn/courses/30/lessons/42890

프로그래머스

 

 

 

위의 방식을 이용한 풀이이다.

 

1차 풀이에서 틀린 이유 

 

1. Set

(1,2)

(2,1)

로 주어진 자료에서 만약 Set 을 사용한다면

(1,2)

(1,2)

 

이되어 중복으로  나온다.

 

2. 얇은 복사

정답을 가지는 전역 변수 2 차원 배열인 answList 에 다음과 같이 추가하면

 

func( arr ) {

   answList.add(arr) ;

}

 

얇은 복사로 배열이 추가가되어 , arr이 변경시 정답 배열 내부의 값도 바뀐다.

 

func( arr ) {

   answList.add(new ArrayList(arr)) ;

}

 

새로 배열을 선언해주자.

import java.util.*;
class Solution {
    List<List<Integer>> anwSets = new ArrayList<>();
    List<List<String>> relMap = new ArrayList<>();
    int row = 0;

    public int solution(String[][] relation) {
        row = relation.length;
        int column = relation[0].length;
        for (int i = 0; i < column; i++) {
            List<String> tmp = new ArrayList<>();
            for (int j = 0; j < row; j++) {
                tmp.add(relation[j][i]);
            }
            relMap.add(tmp);
        }
        int n = column;
        for (int r = 1; r <= column; r++) {
            genCombi(n, r);
        }
        int answer = anwSets.size();
        System.out.println(anwSets);
        return answer;
    }

    private void genCombi(int n, int r) {
        List<Integer> arr = new ArrayList<>();
        generateCom(n, r, 0, arr);
    }

    private void generateCom(int n, int r, int start, List<Integer> arr) {
        if (r == arr.size()) {
            
            for(List<Integer> sets : anwSets) {
                if(arr.containsAll(sets)) return;
            }

            List<List<String>> tmparr = new ArrayList<>();
            for (int i = 0; i < row; i++) {
            List<String> aRow = new ArrayList<>();
                for (Integer item : arr) {
                    String element = relMap.get(item).get(i);
                    aRow.add(element);
                }
                if (tmparr.contains(aRow))
                    return;
                tmparr.add(aRow);
            }

            if (tmparr.size() == row) {
                anwSets.add(new ArrayList<>(arr));
            }
            return;
        }
        for (int i = start; i < n; i++) {
            arr.add(i);
            generateCom(n, r, i + 1, arr);
            arr.remove(arr.size() - 1);
        }
    }
}