[프로그래머스] 체육대회 (JAVA 풀이)

 

문제 접근

 

https://school.programmers.co.kr/learn/courses/15008/lessons/121684

프로그래머스

 

최대 학생수가 10명이고 종목수도 최대 10개까지이므로 모든 경우를 탐색한다고하면

 

첫번 째 종목에서 10명중 1명을 선택하고 두번 째 종목에서 9명중 1명을 선택하고 ... 즉, O(10!)이므로 시간 초과없이 모든 능력치의 합이 최대인 구간을 구할 수 있다.

 

그래서 바로 완전 탐색으로 문제에 접근하였다.

 

문제 풀이

 

위에서 말한대로 각 종목당 현재 고를 수 있는 인원들 각각에 대해 모든 경우를 확인하며 종목들의 모든 인원이 채워졌을 때의 sum 값을 비교하며 최댓값을 구하는 방식으로 구현했다.

 

이를 위해 능력치 합의 최대값을 저장하기 위한 max변수를 선언했고 각 선택지에 따라 더 이상 고를 수 없는(이미 다른 종목에 출전을 한 경우) 학생들의 정보를 담고 있는 Set을 선언해주었다.

 

=> 순서가 유지될필요도 없고 단순히 더 이상 고를 수 없는(이미 다른 종목에 투입된) 학생들을 넣었다가 빼고, contains 메서드만 사용하면 되므로 O(1)에 이게 가능한 Set을 사용했다.

 

dfs로직에서는 cnt를 통해 현재까지 고른 종목들의 수를 나타내고 이게 ability[0].length 즉, 종목의 수와 같아지면 모든 종목에 인원을 배정한 것이므로 그때의 sum(모든 종목에 배정된 학생들의 능력치 합)을 max와 비교하여 더 큰 경우 갱신해준다.

 

만약 아직 모든 종목에 인원이 채워지지 않았다면 for문으로 모든 학생들을 살펴보며 banned라는 Set에 해당 학생이 포함되어 있지 않다면 아직 어떠한 종목에도 배정되지 않은 것이므로 banned에 해당 학생을 추가해주고 재귀 호출을 통해 현재 학생이 이번 종목에 참여하게 되는 걸로 간주하고 그 다음 올 수 있는 경우를 탐색해나갔다.
(다음 종목의 경우를 탐색하기 위해 cnt를 +1 해주었고, sum에 현재 학생의 이번 종목에 대한 능력치를 더해주면서 넘겨주었다.)

 

=> 이 때 banned에 추가했던 학생을 dfs 호출이 끝난 후 다시 remove해줘야 이번 종목에서 다른 학생을 배정하는 경우도 정확하게 탐색이 가능하다.

(만약 이를 해주지 않으면 아직 2번학생이 어떠한 종목에도 배정되지 않은 경우를 살펴보고있는데 이전에 2번학생을 배정했던 경우가 banned에 반영되어 있어서 2번 학생을 고를 수 있는 상황에서도 2번 학생을 제외한 경우의 수를 찾게됨)

 

이제 이렇게 dfs가 종료되었다면 max에는 모든 종목에 대해 각 선수의 능력치 합이 최대인 정답이 들어있으므로 이를 반환해주면 끝난다.

 

전체 코드

 

import java.util.*;

class Solution {
    
    int max = Integer.MIN_VALUE;
    
    void dfs(int cnt, int sum, int[][] ability, Set<Integer> banned) {
        
        if (cnt == ability[0].length) { 
            if (max < sum) {
                max = sum;
            }
            return;
        }
        
        // i번 학생을 cnt번 종목에 배정
        for (int i = 0; i < ability.length; i++) {
            if (!banned.contains(i)) {
                banned.add(i);
                dfs(cnt + 1, sum + ability[i][cnt], ability, banned);
                banned.remove(i);
            }
        } 
    }
    
    public int solution(int[][] ability) {
        
        Set<Integer> banned = new HashSet<>();
        
        // 0번 종목부터 배정 시작
        dfs(0, 0, ability, banned);
        
        return max;
    }
}