[프로그래머스-그리디] 체육복 JAVA 자바

https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

 

👉 풀이

• 최대한 많은 학생이 체육 수업을 듣게 하기 위해서는 적은 번호를 가진 학생끼리 먼저 체육복을 빌려주고 빌려야 한다. 따라서 lost, reserve 배열 오름차순 정렬한다. 정렬 후 체육복을 빌려주기 위해 배열 탐색
• 탐색 전 여분의 체육복이 있는 사람의 체육복이 도난 당했을 경우, 여분의 체육복을 다른 사람에게 빌려줄 수 없으므로 -1 값을 대입해 필터링한다.
• lost와 reserve를 순차적으로 탐색하면서 조건에 만족하면 체육복을 reserve가 lost에게 체육복을 빌려준다. 체육복을 빌려준 경우 다음 탐색에서 제외되기 위해 reserve에 -1을 대입한다.

    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length;
 
        // 최대한 많은 학생이 체육수업을 듣게 할려면 정렬을 해야한다.
        /*
        ex.
        lost = {2,4,5,6}
        reserve = {3,1}
        * */
        Arrays.sort(lost);
        Arrays.sort(reserve);
 
        // 여분의 체육복이 있는 사람의 체육복이 도난 당했을 경우 필터링
        for(int i = 0; i < lost.length; i++){
            for(int j = 0; j < reserve.length; j++){
                if(lost[i] == reserve[j]){
                    answer += 1;
                    lost[i] = -1;
                    reserve[j] = -1;
                    break; // 다음 lost로 넘어가야 함
                }
            }
        }
 
        for(int i = 0; i < lost.length; i++){
            for(int j = 0; j < reserve.length; j++){
                if(lost[i] == reserve[j]-1 || lost[i] == reserve[j]+1){
                    answer += 1;
                    reserve[j] = -1;
                    break; // 다음 lost로 넘어가야 함
                }
            }
        }
 
        return answer;
    }

※ 주의
최대한 많은 학생이 체육 수업을 듣게 하기 위해서 lost, reserve 배열을 오름차순 정렬하고 탐색을 해야한다.

예를 들어
lost = {2,4,5,6}
reserve = {3,1}
체육수업을 많은 학생이 듣기 위해서 2번이 1번의 체육복을, 4번이 3번의 체육복을 빌려야 한다.
그러나 배열이 정렬되어 있지 않으면, 2번이 3번의 여벌 체육복을 먼저 빌리게 되어 4번이 체육복을 빌릴 수 없다.
적은 번호를 가진 학생이 먼저 체육복을 빌려주어야 한다.