[프로그래머스] 암호해독 자바 조합

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

프로그래머스

문제

비밀코드로 사용될 정수의 범위 1 ~ n이 있다.

비밀 코드를 해독하기 위해 시도한 오름차순 숫자 5개의 모음 q 와 각 시도에서 일치한 횟수들의 모음 ans가 있다.

이를 활용하여 비밀 코드가 될 수 있는 후보의 갯수를 구하여라.

 

접근

q[i] 에 ans[i] 개 만큼의 비밀 코드가 있다는 것을 바탕으로 비밀코드 후보들을 만들어야 하는데.. 시작 부터 막혔다.
그래서 GPT의 도움을 받아 해결해보았다.

제안

1. 1~ n까지의 정수를 활용한 5개의 후보값 조합을 만든다.
2. 후보값들을 q와 대조하여 ans 개와 동일한 후보를 찾아 갯수를 더한다.
3. 결과값을 반환한다.

public int solution(int n, int[][] q, int[] ans) {
        int validCount = 0;

        // 1~n 중에서 5개 뽑는 조합 생성
        List<int[]> candidates = generateCombinations(n);

        for (int[] candidate : candidates) {
            boolean isValid = true;
            for (int i = 0; i < q.length; i++) {
                if (countMatches(candidate, q[i]) != ans[i]) {
                    isValid = false;
                    break;
                }
            }
            if (isValid) validCount++;
        }

        return validCount;
    }

    private int countMatches(int[] a, int[] b) {
        Set<Integer> set = new HashSet<>();
        for (int num : a) set.add(num);

        int count = 0;
        for (int num : b) {
            if (set.contains(num)) count++;
        }
        return count;
    }

    private List<int[]> generateCombinations(int n) {
        List<int[]> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), 1, n);
        return result;
    }

    /**
     * 
     * @param result : 조합의 모음
     * @param temp : 조합에 사용될 요소들
     * @param start : 시작범위
     * @param n : 종료범위
     */
    private void backtrack(List<int[]> result, List<Integer> temp, int start, int n) {
        if (temp.size() == 5) {
            int[] arr = new int[5];
            for (int i = 0; i < 5; i++) arr[i] = temp.get(i);
            result.add(arr);
            return;
        }

        for (int i = start; i <= n; i++) {
            temp.add(i);
            backtrack(result, temp, i + 1, n);
            temp.remove(temp.size() - 1);
        }
    }

소감

List에 반복작업을 통해 생성할 수 있는 모든 케이스를 넣어서 조합으로 만들 수 있다는 것을 알게 되었다.
조합을 코딩으로 표현하면 이런 식으로 나타낼 수 있구나 라는 걸 느꼈다.
코딩에 왜 수학이 필요하다고 하는지 점점 느끼게 되는 것 같다.
수학은 어렵고 배울게 참 많구나 싶은 문제였다.