[프로그래머스/LV2] [PCCP 모의고사 1] 2번 - 순열 (Java)

[programmers-lv2] [PCCP 모의고사 1] 2번

🙋‍♂️ 들어가며

문제를 읽어보며 순열의 구조가 떠올랐는데 조건을 보니 10! 이라서 무조건 순열 가능이다.

다만 약간의 실수가 있었다면 아래 코드에 ability[idx][i] 라고 작성해서 계속 인덱스 오류가 나서 디버깅을 하던중 ability[i][idx] 가 맞는 것을 확인하였다.

다음에는 이런 실수를 하지 않도록 해야겠다

✅ 정답 코드

class Solution {
    static int max_sum = Integer.MIN_VALUE;
    static int N, size;
    
    public int solution(int[][] ability) {
        N = ability.length;
        size = ability[0].length;      
        
        // 1. 순열 -> 10! 충분히 가능
        int idx = 0;
        boolean[] visited = new boolean[N];
        int[] selected = new int[size];
        perm(idx, visited, selected, ability);
        return max_sum;
    }
    
    
    // 2. 순열 함수
    static void perm(int idx, boolean[] visited, int[] selected, int[][] ability) {
        // 2-1. idx 다 도달시
        if (idx == size) {
            int temp_sum = 0;
            for (int i = 0; i < size; i++) {
                temp_sum += selected[i];
            }
            max_sum = Math.max(temp_sum, max_sum);
            return;
        }
        
        // 2-2. idx 다 도달 못했으면
        for (int i = 0; i < N; i++) {
            // 2-2-a. 방문했으면 skip
            if (visited[i]) continue;
            
            // 2-2-b. 방문 안했으면
            visited[i] = true;
            selected[idx] = ability[i][idx];
            perm(idx+1, visited, selected, ability);
            
            // 2-2-c. 방문해제
            visited[i] = false;
        }
        
        
    }
    
    
    
}