[Algorithm] 조합(Combination)

조합

조합이란?

• n개의 요소 중 r개의 항목을 뽑는 것을 말한다.
• 순서가 다르더라도 요소가 동일하게 뽑혔다면 같은 케이스로 간주한다.
• A, B → A, B, AB

코드

• result : 결과를 저장하는 셋
• temp : r개를 뽑는 결과 값을 저장하는 배열
• data : 요소 배열
• r : 뽑고자 하는 개수
• depth : 재귀 호출 깊이 값
• start : 다음 반복문의 시작 인덱스
  • i + 1인 이유는 나왔던 값이 또 다시 반복되면 안되기 때문

class Solution {
    public Set<String> solution(String data, int r) {
        Set<String> result = new HashSet<>();
        combination(result, new char[data.length()], data.toCharArray(), r, 0, 0);
        return result;
    }

    private void combination(Set<String> result, char[] temp, char[] data, int r, int depth, int start) {
        if (r == depth) {
            result.add(IntStream.range(0, depth).mapToObj(i -> String.valueOf(temp[i])).collect(Collectors.joining()));
            return;
        }

        for (int i = start; i < data.length; i++) {
            temp[depth] = data[i];
            combination(result, temp, data, r, depth + 1, i + 1);
        }
    }
}

class SolutionTest extends Specification {
    @Unroll
    def "#data, #r-> #result"() {
        expect:
        new Solution().solution(data as String, r as int) == result as Set<String>

        where:
        data  | r | result
        "ABC" | 1 | ["A", "B", "C"]
        "ABC" | 2 | ["AB", "BC", "AC"]
        "ABC" | 3 | ["ABC"]
    }
}

중복 조합

중복 조합이란?

• 조합과 동일하나 이미 선택한 요소가 추가적으로 선택될 수 있다
• 조합 예시
  • A, B → A, B, AB
• 중복 조합 예시
  • A, B → A, B, AB, AA, BB

코드

• 조합 코드와 동일하고, start 값이 i + 1로 넘기던 부분을 i를 넘기도록 변경
• start 값이 i인 이유는 선택한 값을 또 선택 가능하기 때문

class Solution {
    public Set<String> solution(String data, int r) {
        Set<String> result = new HashSet<>();
        combination(result, new char[data.length()], data.toCharArray(), r, 0, 0);
        return result;
    }

    private void combination(Set<String> result, char[] temp, char[] data, int r, int depth, int start) {
        if (r == depth) {
            result.add(IntStream.range(0, depth).mapToObj(i -> String.valueOf(temp[i])).collect(Collectors.joining()));
            return;
        }

        for (int i = start; i < data.length; i++) {
            temp[depth] = data[i];
            combination(result, temp, data, r, depth + 1, i);
        }
    }
}

class SolutionTest extends Specification {
    @Unroll
    def "#data, #r-> #result"() {
        expect:
        new Solution().solution(data as String, r as int) == result as Set<String>

        where:
        data  | r | result
        "ABC" | 1 | ["A", "B", "C"]
        "ABC" | 2 | ["AA", "BB", "CC", "AB", "BC", "AC"]
        "ABC" | 3 | ["AAA", "ABB", "ACC", "AAB", "ABC", "BBC", "CCC", "AAC", "BBB", "BCC"]
    }
}

참고

• https://bcp0109.tistory.com/15
• https://gaybee.tistory.com/29