[programmers] 체육복

문제 풀이 : 2021.05.14

풀이

1. 체육복이 두 개인 학생들과 도난당한 학생들을 배열로 표시
2. 1번의 배열을 이용해서 현재 두 개를 가지고 있는 학생들을 중심으로 앞뒤의 학생이 없는 경우만 탐색
3. 재귀호출을 이용하여 2번 조건을 만족하도록 완전탐색

코드

class Solution {
    static int[] arr;
    static int answer = 0;
    public int solution(int n, int[] lost, int[] reserve) {
        
        arr = new int[n];
        for(int i = 0;i<n;i++){
            arr[i] = 1;
        }
        for(int i = 0;i<reserve.length;i++){
            arr[reserve[i]-1]++;
        }
        for(int i = 0;i<lost.length;i++){
            arr[lost[i]-1]--;
        }
        solve(0);
        
        return answer;
    }
    
    static void solve(int a){
        if(a==arr.length){
            int num = 0;
            for(int i = 0;i<arr.length;i++)
                if(arr[i]>=1)
                    num++;
            
            answer = Math.max(answer, num);
        }
        else{
            if(arr[a] ==2){
                if(a==0){
                    if(arr[a+1]==0){
                        arr[a]--;
                        arr[a+1]++;
                        solve(a+1);
                        arr[a]++;
                        arr[a+1]--;
                    }
                }
                else if(a==arr.length-1){
                    if(arr[a-1]==0){
                        arr[a]--;
                        arr[a-1]++;
                        solve(a+1);
                        arr[a]++;
                        arr[a-1]--;
                    }
                }
                else{
                    if(arr[a+1]==0){
                        arr[a]--;
                        arr[a+1]++;
                        solve(a+1);
                        arr[a]++;
                        arr[a+1]--;
                    }
                    if(arr[a-1]==0){
                        arr[a]--;
                        arr[a-1]++;
                        solve(a+1);
                        arr[a]++;
                        arr[a-1]--;
                    }
                }
            }
            solve(a+1); 
        }
    }
}