[프로그래머스] 체육복

문제 :  전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

풀이 : 해당 문제는 탐욕법으로 풀어야 하는 문제이다. 

• 우선 lost,reserve를 정렬
• 여벌이 있는 학생이 도난 당할 수 있기에 먼저 처리 (체육복을 빌려주고, 빌린 걸 받은 사람은 -1 처리)
• 앞사람, 뒷사람까지 빌려줄 수 있으므로 해당 조건에 만족하는 지 비교 후 빌림 처리 (-1로 처리)
• 기존에 있던 학생 수 (n)에서 체육복을 못빌린 사람을 제외하는 방식으로 최종 결과 도출

 

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
       
        Arrays.sort(lost);
        Arrays.sort(reserve);

        for(int i=0; i<lost.length; i++){
            for(int k=0; k<reserve.length; k++){
               if(lost[i]==reserve[k]){
                   lost[i]=-1;
                   reserve[k]=-1;
                   break; 
                }
            }
        }
        for(int i=0; i<lost.length; i++){
                if(lost[i]==-1) continue;
                for(int k=0; k<reserve.length; k++){
                    if(reserve[k]==-1) continue;
                    if(reserve[k]==lost[i]-1||reserve[k]==lost[i]+1){
                        lost[i]=-1;
                        reserve[k]=-1;
                        break;
                    }
                } 
        }
        int answer=n;
        for(int l : lost){
            if(l!=-1) answer--;
        }
        return answer;
    }
}

 

 

---

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42862