[programmers] 탐욕법(Greedy) > 체육복

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        
        Arrays.sort(lost);
        Arrays.sort(reserve);
        
        ArrayList<Integer> l = new ArrayList<>();
        ArrayList<Integer> r = new ArrayList<>();
        for(int i=0;i<reserve.length;i++){
            r.add(reserve[i]);
        }
        for(int i=0;i<lost.length;i++){
            l.add(lost[i]);
        }
        
        for(int i=0;i<l.size();i++){
            for(int j=0;j<r.size();j++){
                 if(l.get(i) == r.get(j)){
                     l.remove(i);
                     r.remove(j);
                     i--;
                     j--;
                     break;
                 } 
            }
        }
        
        int num = 0;
        for(int i=0;i<l.size();i++){
            for(int j=0;j<r.size();j++){
                if(r.get(j)-1 == l.get(i) || r.get(j) == l.get(i) || r.get(j)+1 == l.get(i)) {
                    r.remove(j);
                    l.remove(i);
                    i--;
                    j--;
                    break;
                }
            }
        }
        
         answer = n - l.size();
        return answer;
    }
}

 

효율성이 좋지 않은 것 같아서 다시 풀 예정.

 

+추가

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n;
        int student[] = new int[n+2];
        
        for(int i=0;i<lost.length;i++){
            student[lost[i]]--;
        }
        for(int i=0;i<reserve.length;i++){
            student[reserve[i]]++;
        }
        
        for(int i=1;i<=n;i++){
            if(student[i-1] == 1 && student[i] == -1){
                student[i] = 0;
                student[i-1] = 0;
            } else if(student[i+1] == 1 && student[i] == -1){
                student[i] = 0;
                student[i+1] = 0;
            }
        }
        
        for(int i=1;i<=n;i++){
            if(student[i] < 0) answer--;
        }
        
        return answer;
    }
}

student[i] 기준, student[i-1] 을 먼저 비교 해야함.