체육복 - Greedy, DFS

import java.util.*;
import java.util.stream.*;
class Solution {
    static List<Integer> visited=new ArrayList<>();
    static int answer=0;
    public int solution(int n, int[] lost, int[] reserve) {
        //바로 앞 번호 학생이나 뒷번호 학생에게만 체육복 대여 가능
        //최대한 많은 사람 빌려주기
        //여벌 체육복 가져온 사람 체육복 도난 가능 -> 빌려줄 수 없다.
        // int answer=0;
        List<Integer> list = new ArrayList<>();
        for(int i=1;i<=n;i++){
            list.add(i);
        }

        for(int i=0;i<lost.length;i++){
            list.remove(new Integer(lost[i]));
        }
        
        DFS(0, reserve[0], reserve,list, n);
        return answer;
}
public void DFS(int L, int index, int[] reserve, List<Integer> list, int n){
        System.out.println("list: "+list.toString());
        // System.out.println(L+" "+index);
       
        if(index>0&&index<=n&&!list.contains(index)){
            list.add(index);
            answer=Math.max(answer,list.size());
        System.out.println("result: "+index+" "+
                           list.toString()+" "+answer);
        }
        if(reserve.length==L || index<0 || index>=n){
            return;
        }
        else{
            System.out.println("false"+list.toString()+" "+L);
            DFS(L+1, reserve[L]+1,reserve,list,n);
if(reserve[L]+1<n&&list.contains(reserve[L]+1))
    list.remove(new Integer(reserve[L]+1));
            DFS(L+1, reserve[L]-1,reserve,list,n);
        }
    }
}

도난당했는데 여분있는 사람 무조건 거르고 시작

 

import java.util.*;
class Solution {
    static int answer = 0;
    static List<Integer> visited= new ArrayList<>();
    public int solution(int n, int[] lost, int[] reserve) {
        
        //바로 앞 번호 학생이나 뒷번호 학생에게만 체육복 대여 가능
        //최대한 많은 사람 빌려주기
        //여벌 체육복 가져온 사람 체육복 도난 가능 -> 빌려줄 수 없다.
        // int answer=0;
        List<Integer> list = new ArrayList<>();
        List<Integer> rental = new ArrayList<>();
        for(int i=1;i<=n;i++){
            list.add(i);
        }
        for(int i=0;i<lost.length;i++){
            for(int j=0;j<reserve.length;j++){
                if(lost[i]==reserve[j]) {
                    lost[i]=0;
                    reserve[j]=0;
                }
            }
            if(lost[i]!=0) list.remove(new Integer(lost[i]));
        }
        for(int i=0;i<reserve.length;i++){
            if(reserve[i]!=0)rental.add(reserve[i]);
        }

        // System.out.println("List: "+list.toString());
        answer=list.size();
        DFS(0, rental.get(0)+1,list, rental,n);
        
        DFS(0, rental.get(0)-1,list, rental,n);
        return answer;
    }
    public void DFS(int L, int index, List<Integer> list, List<Integer> rental,int n){
        // System.out.println("DFS전 "+index+" "+L+" "+list.toString()+" "+rental.toString());
        
        if(!visited.contains(L)&&index>0 && index<=n&&!list.contains(index)){
            list.add(index);
            answer=Math.max(answer, list.size());
            visited.add(L);
            System.out.println("DFS");
        }
        // System.out.println("DFS후"+index+" "+list.toString()+" "+rental.toString());
        
        if(L+1>=rental.size()||list.size()==n) return;
        DFS(L+1, rental.get(L+1)+1,list,rental,n);
if(visited.contains(L)){
  list.remove(new Integer(rental.get(L+1)+1));
    visited.remove(new Integer(L));
} 
        
        DFS(L+1, rental.get(L+1)-1,list,rental,n);
    }
}

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {        
        int cnt=n-lost.length;
        int reserve_arr[]=new int[reserve.length];
        int lost_arr[]=new int[lost.length];

        Arrays.sort(lost);
        Arrays.sort(reserve);

        for(int a=0;a<lost.length;a++){
            for(int b=0;b<reserve.length;b++){
                if(lost[a]==reserve[b]){
                    reserve_arr[b]=1;
                    lost_arr[a]=1;
                    cnt+=1;
                    break;
                } //if                    
            } //for
        } //for

        for(int a=0;a<lost.length;a++){
            for(int b=0;b<reserve.length;b++){
            int gap=Math.abs(lost[a]-reserve[b]);
            if( gap==1 && reserve_arr[b]==0 && lost_arr[a]==0 ){
                System.out.println(lost[a]+" : "+reserve[b]);
                cnt+=1;
                lost_arr[a]=1;
                reserve_arr[b]=1;
                break; 
            } //if                
            } // for
        } // for
        return cnt;
    }
} // class

 

---

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n-lost.length;
        Arrays.sort(lost);
        Arrays.sort(reserve);
        
        List<Integer> los = new ArrayList<>();
        List<Integer> res = new ArrayList<>();

        Arrays.stream(reserve).forEach(a-> res.add(a));
        
        for(int x :lost){
            if(res.contains(x)){
                res.remove(new Integer(x));
                answer++;
            }else{
              los.add(x);  
            }
        }
        
        for(int x:los){
            if(res.contains(x-1)){
                res.remove(new Integer(x-1));
                answer++;
            }else if(res.contains(x+1)){
                res.remove(new Integer(x+1));
                answer++;
            }
        }
        
        return answer;
    }
}